the basement > Logic Puzzles

[SPOILER] Twist on a Classic

(1/1)

redyoshi49q:
This is the spoiler thread to the Twist on a Classic puzzle.

Arbutus:
Not being mathematically inclined, I probably spent a lot longer thinking about this than I needed to. :D But here's what I'm thinking.

CUE THE BLACK TEXT

It seems like one's success with this problem depends on being able to figure out what you're hinting at with the "31 apples in 5 bags" thing. I'm guessing the point of that problem is that you have 31 apples in 5 bags, and by setting aside different numbers of, and combinations of, bags, you can dispense any number of apples between 1 and 31. As Bob hints, the five bags contained 1, 2, 4, 8, and 16 apples. This plays off the fact that 25 = 32, but the sum of all five factors of 32 (excluding 32 itself) equals 32 - 1 = 31. The same holds true for any n equal to 2x.

So Billy's puzzle looks like an extension of that fact; x = 10, 210 = 1,024, and therefore 10 bags and 1,023 apples will allow you to make any number between 1 and 1,023. But no: Billy suggests that there's no way to dispense only one apple, but that 1,025 apples can be dispensed. I think you can fix this by simply having a bag with three apples rather than a bag with one apple, which gives you the following sequence:
2  3  4  8  16  32  64  128  256  512  =  10 bags, 1,025 apples

The fact that Billy cannot dispense any number of apples greater than 2,000 is, I hope, a red herring.

Like I said, I'm not mathy enough to actually prove this, nor am I patient enough to brute-force it. So... maybe it's right? ;)

redyoshi49q:
(*ding ding ding!*)

Arbutus, you have found a solution to this puzzle with the faster of two methods.  Your solution does happen to be the single valid possibility (aside from the possible inclusion of empty bags, which in retropsect, I should have eliminated via additional criterion).  Though this solution is indeed the correct solution Bob supplied, Bob was also able to justify that combinaton of bagged apples as the only possible one (excluding emptly bags) that could meet all of the criterion.

For the curious, the other (considerably longer and more complicated but more thorough) method that the ficticious Bob used to arrive at his solution is outlined below:

(*spoiler warning*)

Let's assume that the puzzler is completely unaware of the logic hinted at by the lead-in problem that involves 5 bags and 31 apples.  The only information that the puzzler has to solve this problem is the number of apples that can and cannot be given through combinations of the available bags.  Since there are a large multitude of combinations for large numbers of apples, the lowest numbers of apples are considered first for simplicity's sake.

The only way it is possible for a single apple to be given in this setup is if there is a bag with a single apple in it.  Since giving a single apple is impossible, it must be concluded that no bag has exactly one apple.

Similarly, there are only two ways in which two apples can be given, namely, through two bags with one apple each or one bag with two apples.  Since it has been previously concluded that no bag has exactly one apple, having at least one bag with two apples is the only remaining way in which two apples can be given.  Since it is possible to give two apples, this must be the case.

There are three ways in which three apples can be given (3 bags with 1 apple each, bags with 1 and 2 apples, and a single bag with 3 apples), but there is only one way in which three apples can be given if there are no bags with only one apple in them.  With a similar logic as before, it is concluded that at least one bag must have three apples.

Four bags is the first point at which a real decision must be made.  Excluding the possibilities that require a bag with 1 apple, there are two ways in which four apples can be given.  The case of two bags with two apples each (as well as other possibilities) will be considered later.  For now, it will be assumed that the puzzler has decided that there is a bag with four apples in it.

At this point, it is possible for 2, 3, 4, 5 (2+3), 6 (2+4), 7 (3+4), and 9 (2+3+4) apples to be given.  However, no other possibilities exist with the three bags previously determined to exist.  More specifically, it is impossible for either exactly 1 or exactly 8 apples to be given.  There is a "gap" in the possibilities at 8 apples, and an insightful puzzler will realize that this "gap" is very much like the one that is called for in the final solution.

The conundrum then becomes moving this "gap" from 8 apples to 1,024 apples.  The way to "move the gap" from this point is to throw in a bag with 8 apples.  Since the other three bags are unable to produce exactly 8 apples or exactly 16 apples through any combination, the new bag of 8 apples is unable to comine with any combination of the previous three bags to produce exactly 16 apples.  However, the possibilites of 8, 10 (8+2), 11 (8+3), 12 (8+4), 13 (8+5), 14 (8+6), 15 (8+7), and 17 (8+9) are produced through combinations of the 8 apple bag and the previous 3 bags.  When all combinations are considered, any possibility between 2 and 17 except 16 is now possible.  The "gap" is effectively moved from 8 apples to 16 apples.  Adding any other number of apples will close the gap at 8 apples without adding a new gap to take its place.  Similar logic produces bags with 16, 32, 64, 128, 256, and 512 apples.  Conveniently, every condition of the original problem is met at this point.

However, the possibility of there being other bags with apples (and therefore, different possible solutions) has yet to be eliminated.  To prove that no other bags of apples can be be added to this solution without losing a point of criterion, two separate cases will be considered.  Let's say that another bag of n apples (where n is between 1 and 1,022) is added to this system.  Since every possible number of 1,024 - n apples (which translates to every possibile combination of apples between 2 and 1,023) is attainable with the previous 10 bags, adding this particular combination of 1,024 - n apples with the new bag of n apples creates a combination of 1,024 apples.  Since this possibility does not exist, an additional bag will break the solution if it has between 1 and 1,022 apples.  If the additional bag has more than 1,022 apples, then the sum of all of the apples will be at least 2,048 (1,025 from previous ten bags + 1,023 from new bag).  Since giving all of the bags will result in more than 2,000 apples being given, adding a bag with more than 1,022 apples will also break the solution.

What if the puzzler used a different method to achieve the different combinations of apples?  By no means is it necessary to use a binary system necessary to make available every possibility of apples.  For example, suppose that the bags had 2, 3, 4, 5, 9, 10, 20, 30, 40, 100, 200, 300, and 300 apples in them.  This particular set of bags allows for any combination of apples between 2 and 1,023 to be given through some combination of these bags.  In fact there are several numbers of apples (such as 11) that can be given through several combinations of these bags (2+9 and 2+3+4).  However, there is still the issue of giving 1,025 apples.  If an additional bag of apples were to be added to allow a combination of 1,025 apples, then it would also become possible for 1,024 apples to be given.   If a bag of 1,025 apples were to be added in order to create the necessary gap between 1,023 and 1,025 apples, then it would be possible to give more than 2,000 apples.  (The 2,000 apple limit was more than just a red herring, Arbutus.)   The logic to these two conclusions is similar to the the logic provided in the previous paragraph.  Because of this issue, it becomes apparent that the correct solution must create the necessary "gap" by means other than building a combination of 1,023 apples and adding a bag of 1,025 apples.  The only way to have this gap is to utilize the one that is created when there is a bag of 2 apples and a bag of 3 apples (this is why a bag of 4 apples was created several steps ago as opposed to adding a second bag of 2 apples).  Attempting to create a useful gap through other means proves unsuccessful.

If you have managed to traverse and comprehend this entire proof, congratulations!  Even more kudos to you if you have managed to figure out part of it before it was posted!

Yip:
I am not familiar with this "classic problem" you were referring to. However, I am very familiar with binary so I very quickly arrived at this:
--- Code: ---3 2 4 8 16 32 64 128 256 512   Total
------------------------------------
. 2 . . .  .  .  .   .   .   = 2
3 . . . .  .  .  .   .   .   = 3
. . 4 . .  .  .  .   .   .   = 4
3 2 . . .  .  .  .   .   .   = 5
. 2 4 . .  .  .  .   .   .   = 6
3 . 4 . .  .  .  .   .   .   = 7
. . . 8 .  .  .  .   .   .   = 8
3 2 4 . .  .  .  .   .   .   = 9
. 2 . 8 .  .  .  .   .   .   = 10
3 . . 8 .  .  .  .   .   .   = 11
. . 4 8 .  .  .  .   .   .   = 12
3 2 . 8 .  .  .  .   .   .   = 13
. 2 4 8 .  .  .  .   .   .   = 14
3 . 4 8 .  .  .  .   .   .   = 15
. . . . 16 .  .  .   .   .   = 16
3 2 4 8 .  .  .  .   .   .   = 17
--- End code ---

At this point I was able to clearly see the emerging pattern and thus the end of it:

--- Code: ---3 2 4 8 16 32 64 128 256 512   Total
------------------------------------
3 . 4 8 16 32 64 128 256 512 = 1023
. . . . .  .  .  .   .   .   = n/a
3 2 4 8 16 32 64 128 256 512 = 1025
--- End code ---

This satisfies all criteria listed, and on my first try. ;)

I would explain it further but I think Arbutus' explanation sums it up well.