Weighing problem

[jason]

Hi guys! Happy new year! Nice site!

I was given this one a while ago, but haven't been able to figure any solution so far

A young boy is walking to school from his house in the countryside and has to pass through a small forest. He has a snack with him, which he must eat at the noon break, but he is hungry so he eats it while walking to school.
He realizes, of course, that there will be nothing left to eat at the break!
Fortunately, the forest is full of pears that have fallen off the trees, one every few steps, on his way to school. Some of them are rotten, though, which cannot be discerned from the good ones. Only one pear can fit in his lunch box, so he must take with him exactly one pear. Furthermore, he has with him a small balance scale which he needs for the class of physics. He knows that all good pears have exactly the same weight and also that all rotten pears have different weights from the good ones (can also be different from each other but not necessarily). Knowing also that there are more good pears than rotten, how can he select exactly one good pear without walking back and forth?

Anyone?
Please excuse any language mistakes but I am Italian

[Guest]

The trick is to consider what happens when you have two pears with different weights. There are only two possibilities:
(A) both are rotten
or
(B) one is good and the other is rotten
In both cases if we ignored both those pears (pretended like they didn't exist) the number of good pears is still more than the number of bad pears.

For example if we knew (by magic) that there were in total 4 good pears and 3 bad pears, and we encounter two pears of different weights, then after we ignore them we would know there are 4 good pears and 1 bad if we are in case (A) or that there are 3 good and 2 bad if we are in case (B). In either case there was still more good pears than bad.

So the solution is to do the following:

1) Pick up a pear and put it into your lunch box.
Keep track of how many pears you've encountered (so far it is 1).
Go to step 2.

2) Try to move to the next pear.
If there are no more pears: Every pear you've encountered is the same weight as the one in your lunch box, so it must be a good pear, and you are done.
If there is another pear: Go to step 3.

3) Weigh the pear you just found with the pear in your lunch box.
Remember to keep track of how many pears you've encountered by adding one to the number encountered so far.
If the pears weigh the same: (Notice that all the pears you've encountered weigh the same as the one in your lunch box.) Go to step 2.
If the pears have different weights: (Notice that all the pears you've encountered weigh the same as the one in your lunch box except for this last one.) Go to step 4.

4) If we've only encountered 2 pears: Ignore them (pretend they don't exist), throw away the pear in your lunch box, reset the number of pears encountered to 0, and go to step 1.
If we've encountered more than 2 pears: All the pears you've encountered weigh the same except for the very last pear you found, so ignore the last pear and the second last pear (they must have different weights). Subtract two from the number of pears encountered (to account for the pears we are now pretending don't exist), and go to step 2. (Notice that after we ignored the two pears we are back in the situation that all pears we've found have the same weight).


As an example suppose the pears weigh 1, 1, 1, 5, 4, 3, 2, 2, 4, 2, 2, 2, 2, 2, 2:
1 ) Find pear (it weighs 1), you put it in your lunch box. In total you've found 1 pear [weights: 1].
2 ) Find pear (it weighs 1). It weighs the same as the pear in your lunch box. In total you've found 2 pears [weights: 1, 1].
3 ) Find pear (it weighs 1). It weighs the same as the pear in your lunch box. In total you've found 3 pears [weights: 1, 1, 1].
4 ) Find pear (it weighs 5). It has a different weight to the pear in your lunch box. You pretend the last two pears don't exist. In total you've found 2 pears [weights: 1, 1].
5 ) Find pear (it weighs 4). It has a different weight to the pear in your lunch box. You pretend the last two pears don't exist. In total you've found 1 pear [weights: 1].
6 ) Find pear (it weighs 3). It has a different weight to the pear in your lunch box. You pretend the last two pears don't exist. In total you've found 0 pears.
7 ) Find pear (it weighs 2), you put it in your lunch box. In total you've found 1 pear [weights: 2].
8 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 2 pears [weights: 2, 2].
9 ) Find pear (it weighs 4). It has a different weight to the pear in your lunch box. You pretend the last two pears don't exist. In total you've found 1 pear [weights: 2].
10 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 2 pears [weights: 2, 2].
11 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 3 pears [weights: 2, 2, 2].
12 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 4 pears [weights: 2, 2, 2, 2].
13 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 5 pears [weights: 2, 2, 2, 2, 2].
14 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 6 pears [weights: 2, 2, 2, 2, 2, 2].
15 ) Find pear (it weighs 2). It weighs the same as the pear in your lunch box. In total you've found 7 pears [weights: 2, 2, 2, 2, 2, 2, 2].
16 ) No more pears found. In total there are 7 pears all weighing the same as the pear in your lunch box, so it must be a good pear.

In reality there were 8 good pears and 7 rotten pears, but because we pretended some pears didn't exist, we end up pretending that there were only 7 pears all of which were good.

Hope this helped,

R. Baber.

[jason]

Your solution is brilliant!! I am impressed!!

Just a small question (in your example):
I put the first pear (weighing 1) in my lunch box. Then, until I find the one weighing 5 (in which case, I will throw this one and its previous, weighing 1), what do I do with the other 2 (weighing 1)? I carry them with me? What if there were 21 pears in total and the first ones to encounter were, say, 5, weighing 1? Would I carry them all with me? Would it be correct to keep only the first one (or anyone, since they all weigh the same) and keep it until I encounter one of different weight? This way, if it turns out that this one was a good one, I keep it. (I am asking this, because I am under the impression that the riddle says that the boy can only carry one pear in his lunch box, so I am not sure if this implies that he can carry only one pear in his hands also).

Thanks!!

[Guest]

My solution only requires you to carry at most one pear at a time. You only ever add a pear to your lunch box (i.e. carry a pear) if you are in step 1. You remember (some of) the other pears of the same weight but you don't carry them with you.

The square brackets in my example are simply there to illustrate that at each step, the list of pears we claim to have encountered are all the same weight.

If we label the 15 pears in my example A, B, C, ..., M, N, O respectively, then at the end of each step of the example the pears that you remember encountering, and the pear you are holding is as follows:

1 ) Holding A. Remember A.
2 ) Holding A. Remember A, B.
3 ) Holding A. Remember A, B, C.
4 ) Holding A. Remember A, B.
5 ) Holding A. Remember A.
6 ) Holding Nothing. Remember no pears.
7 ) Holding G. Remember G.
8 ) Holding G. Remember G, H.
9 ) Holding G. Remember G.
10 ) Holding G. Remember G, J.
11 ) Holding G. Remember G, J, K.
12 ) Holding G. Remember G, J, K, L.
13 ) Holding G. Remember G, J, K, L, M.
14 ) Holding G. Remember G, J, K, L, M, N.
15 ) Holding G. Remember G, J, K, L, M, N, O.
16 ) No more pears found. We are holding G a good pear, we remember 7 good pears G, J, K, L, M, N, O.

Hope this helped,

R. Baber.

[jason]

You are brilliant!!