[Guest]

This is a variation on a puzzle posted here last year.

You have 3 eggs which are identical. There is a building with N floors. You will conduct tests by dropping eggs from various floors to see if they will break. If you drop an egg and it breaks, you can't use again. But, if it doesn't break, it is as good as new and can be used again. You only have time for 6 tests.

What is the largest N, where you can still guarantee that you will determine the exact highest floor from which you can drop an egg without it breaking?

[Guest]

8

[preflop]

I am sure I haven't thought through all the ramifications but..

12

[Guest]

drop from floor 9. if doesn't break go to floor 18. if does break, go to floor 12. if doesnt break, go floor 15. if breaks, try floor 13. then 14.

I'd say 18 floors.

[Guest]

Sry,16.

[Guest]

You have six tests so I would say six floors

[Guest]

I think you can throw it from the 4th floor, and if it breaks, test 2nd. If it breaks, try 1st, if it doesn't, try 3rd. If it doesn't break, go to 8th and repeat (6th if it breaks then 5th or 7th). Since you have to save 2 throws for when the first egg breaks, you can go up to 16th.

[Guest]

I'm assuming that dropping an egg on floor 1 will not result in a break, and that floor 1 is the bottom floor of the building.

The largest number of floors N for which you could guarantee resolution down to 1 floor would be

22

If a test is required on floor 1, make it 21.

I find it helpful to visualize this problem as a binary tree, branching one way for breaks (say left) and the other for non-breaks. Then the number of left branches could never go higher than 3 and the depth of the total tree could not exceed 6 (6 breaks).

Leaves of the tree represent the highest floor with no breakage. Left branches are breaks, right are non-breaks. If you have to test on floor 1, subtract 1 from each number and change leaf 0 to 1.

                           8                                                  

                           |                                                  

    /--------------------------------------------\                            

    4                                            15                           

    |                                            |                            

  /-----------\                  /--------------------------------\           

  2           6                 11                                22          

  |           |                 |                                  |          

/---\      /------\      /---------------\                    /-----------\   

1   2      5      7      9               13                  18           22  

    |      |      |      |               |                   |                

  /---\  /---\  /---\  /---\         /-------\        /---------------\       

  2   3  4   5  6   7  8   10       12       14      16               20      

                           |        |        |        |               |       

                         /---\    /---\    /---\    /---\         /-------\   

                         9   10  11   12  13   14  15   17       19       21  

                                                        |        |        |   

                                                      /---\    /---\    /---\ 

                                                     16   17  18   19  20   21

[Guest]

I'm assuming that dropping an egg on floor 1 will not result in a break, and that floor 1 is the bottom floor of the building.

The largest number of floors N for which you could guarantee resolution down to 1 floor would be

22

If a test is required on floor 1, make it 21.

I find it helpful to visualize this problem as a binary tree, branching one way for breaks (say left) and the other for non-breaks. Then the number of left branches could never go higher than 3 and the depth of the total tree could not exceed 6 (6 breaks).

Leaves of the tree represent the highest floor with no breakage. Left branches are breaks, right are non-breaks. If you have to test on floor 1, subtract 1 from each number and change leaf 0 to 1.

                           8                                                  

                           |                                                  

    /--------------------------------------------\                            

    4                                            15                           

    |                                            |                            

  /-----------\                  /--------------------------------\           

  2           6                 11                                22          

  |           |                 |                                  |          

/---\      /------\      /---------------\                    /-----------\   

1   2      5      7      9               13                  18           22  

    |      |      |      |               |                   |                

  /---\  /---\  /---\  /---\         /-------\        /---------------\       

  2   3  4   5  6   7  8   10       12       14      16               20      

                           |        |        |        |               |       

                         /---\    /---\    /---\    /---\         /-------\   

                         9   10  11   12  13   14  15   17       19       21  

                                                        |        |        |   

                                                      /---\    /---\    /---\ 

                                                     16   17  18   19  20   21

First of all, no one has the answer yet. I'll wait till tomorrow to post my answer.

Here is one clarification, that some have asked for. The egg could break falling from the 1st floor and it might not break falling from the top floor. You must test for everything.

[plainglazed]

humility aside, 26? as long as the egg doesn't break, try floors 6,12,18,22,24,26. If it breaks anywhere along the way, think you still have enough tries to verify at what floor.

EDIT: left out a floor

Edited July 23, 2010 by plainglazed

[plainglazed]

32? trying floors 10,18,24,28,30, then 32.

[Guest]

lucky number ten

if you drop it from ten and it breaks then you only have 2 eggs left ... and 5 tries left

if you drop it from five and it breaks then you only have 1 eggs left ... and 4 tries left

if you drop it from one and it breaks then the answer is floor zero and zero eggs left ... and 3 tries left else

if you drop it from two and it breaks then the answer is floor one and zero eggs left ... and 2 tries left else

if you drop it from three and it breaks then the answer is floor two and zero eggs left ... and 1 tries left else

if you drop it from four and it breaks then the answer is floor three and zero eggs left ... and 0 tries left else

if you drop it from four and it doesn't break then the answer is floor four and one egg left .and 0 tries left

else if drop ten breaks and five doesn't break then you test 6,7,8,9 in that order to determine which is the highest

[Guest]

lucky number ten

if you drop it from ten and it breaks then you only have 2 eggs left ... and 5 tries left

if you drop it from five and it breaks then you only have 1 eggs left ... and 4 tries left

if you drop it from one and it breaks then the answer is floor zero and zero eggs left ... and 3 tries left else

if you drop it from two and it breaks then the answer is floor one and zero eggs left ... and 2 tries left else

if you drop it from three and it breaks then the answer is floor two and zero eggs left ... and 1 tries left else

if you drop it from four and it breaks then the answer is floor three and zero eggs left ... and 0 tries left else

if you drop it from four and it doesn't break then the answer is floor four and one egg left .and 0 tries left

else:

if you drop it from ten and it breaks and five doesn't break then you test 6,7,8,9 in that order to determine which is the highest

This is of course assuming that it maybe be zero floors that it may drop from

else:

Then it could be lucky number 11

But if we 'assume' that it will at least drop from one of the N floors without breaking then we can say we don't need to test floor one

therefore:

if you drop it from eleven and it breaks then you have only two eggs left and 5 tries left

if you drop it from six and it breaks then you have only one eggs left and 4 tries left

if you drop it from two and it breaks then the answer is floor one and you have zero eggs left ... and 3 tries left else

if you drop it from three and it breaks then the answer is floor two and you have zero eggs left ... and 2 tries left else

if you drop it from four and it breaks then the answer is floor three and you have zero eggs left ... and 1 tries left else

if you drop it from five and it breaks then the answer is floor four and you have zero eggs left ... and 0 tries left else

if you drop if from five and it doesn't then the answer is floor five and you have one eggs left ... and 0 tries left

else:

if you drop if from eleven and it breaks and six doesn't break then test 7,8,9,10 in that order to determine which is the hightest

edit: spacing

Edited July 23, 2010 by PVRoot

[Guest]

41 floors max. Explanation to follow.

[Guest]

41 floors max. Explanation to follow.

Lets assume a worst-case scenario where the egg breaks every drop and work our way upwards from there. So we drop our first egg from some floor, don't know which yet, and it breaks. Drat! Oh well, we've still got time for 5 drops and 2 eggs left. We take the second egg and drop it from some floor, we don't know which yet, and it breaks. Drat! Oh well, we've still got time for 4 more drops and 1 egg left. But now we can't afford to lose this last egg without learning what we need to. We have 4 drops left so we drop it from the first floor up to the 4th. If it breaks on one of those floors, the highest safe floor is the floor beneath where it broke! If it doesn't, then the highest safe distance is on the 4th floor or higher and below where our second egg broke on the second drop (not inclusive). So that means we needed to drop our second egg from the 5th floor to know the exact floor in all cases. Moving on.

Now that we know that the second egg is dropped on the 5th floor if the 1st one broke we look at what would happen if it didn't break from the 5th floor. Well, we drop the egg again from some height, not sure what height yet, and assume it breaks. Drat! Oh well, we've still got time for 3 drops with our last egg. We drop from the 6th floor (since we can't afford to lose this egg without finding the exact floor), then the 7th then the 8th. If it doesn't break then the highest safe distance is on the 8th floor or higher and below where our second egg broke on the third drop (not inclusive). So that means we needed to drop our egg from the 9th floor if it survived the 5th floor drop.

Following this logic we get the following progression: If the 1st egg breaks on the 1st drop, then drop the second egg from the 5th floor. If it survives drop it from the 9th floor. If it survives drop it from the 12th floor. If it survives drop it from the 14th floor. If it survives drop it from the 15th floor. If it's still intact then the highest safe distance is on the 15th floor or higher and below where our first egg broke on the first drop (not inclusive). So that means we needed to drop our very first egg from the 16th floor.

When the first egg survives the first drop then we do everything we did above but with one less drop to use. The whole method follows an easy pattern and so we get the following progression: If the first egg survives on the 1st drop (16th floor), then drop it from the 27th floor. If it survives drop it from the 34th floor. If it survives drop it from the 38th floor. If is survives drop it from the 40th floor. If it survives drop it from the 41st floor. If it's still intact we'd better hope the building only has 41 floors, because we're out of time!

As usual, sorry if my explanation is a bit awkward to follow

[plainglazed]

but suspect am confident Tuck once again is pitching from a higher floor. Start at floors 16,27,34,38,40,41. If it breaks anywhere along the way, you should still have enough eggs and tries to determine which is the highest floor.

EDIT: fixed tags

Edited July 23, 2010 by plainglazed

[Guest]

                     16

      _______________|________________

     5                                27

 ____|____                  __________|_____________  

 1        9                20                      34

 |     ___|___          ___|____             _______|_______ 

 2    6      12        17      23           30             38

 |    |   ___|___       |     __|____      __|__         __|___

 3    7  10     14     18    21    25     28   32       36     40

 |    |   |   __|__     |     |   __|__   |   __|__   __|__   __|__

 4    8  11  13   15   19    22  24   26  29  31  33 35   37 39  41

[Guest]

Lets assume a worst-case scenario where the egg breaks every drop and work our way upwards from there. So we drop our first egg from some floor, don't know which yet, and it breaks. Drat! Oh well, we've still got time for 5 drops and 2 eggs left. We take the second egg and drop it from some floor, we don't know which yet, and it breaks. Drat! Oh well, we've still got time for 4 more drops and 1 egg left. But now we can't afford to lose this last egg without learning what we need to. We have 4 drops left so we drop it from the first floor up to the 4th. If it breaks on one of those floors, the highest safe floor is the floor beneath where it broke! If it doesn't, then the highest safe distance is on the 4th floor or higher and below where our second egg broke on the second drop (not inclusive). So that means we needed to drop our second egg from the 5th floor to know the exact floor in all cases. Moving on.

Now that we know that the second egg is dropped on the 5th floor if the 1st one broke we look at what would happen if it didn't break from the 5th floor. Well, we drop the egg again from some height, not sure what height yet, and assume it breaks. Drat! Oh well, we've still got time for 3 drops with our last egg. We drop from the 6th floor (since we can't afford to lose this egg without finding the exact floor), then the 7th then the 8th. If it doesn't break then the highest safe distance is on the 8th floor or higher and below where our second egg broke on the third drop (not inclusive). So that means we needed to drop our egg from the 9th floor if it survived the 5th floor drop.

Following this logic we get the following progression: If the 1st egg breaks on the 1st drop, then drop the second egg from the 5th floor. If it survives drop it from the 9th floor. If it survives drop it from the 12th floor. If it survives drop it from the 14th floor. If it survives drop it from the 15th floor. If it's still intact then the highest safe distance is on the 15th floor or higher and below where our first egg broke on the first drop (not inclusive). So that means we needed to drop our very first egg from the 16th floor.

When the first egg survives the first drop then we do everything we did above but with one less drop to use. The whole method follows an easy pattern and so we get the following progression: If the first egg survives on the 1st drop (16th floor), then drop it from the 27th floor. If it survives drop it from the 34th floor. If it survives drop it from the 38th floor. If is survives drop it from the 40th floor. If it survives drop it from the 41st floor. If it's still intact we'd better hope the building only has 41 floors, because we're out of time!

As usual, sorry if my explanation is a bit awkward to follow

Excellent explanation! And phillip1882's visual solution is really nice as well. Yes, it's surprisingly high. The original problem used two eggs and had 36 floors and asked the question, how many searches do you need? The answer is surprisingly low, LOL.

I got to thinking how adding a third egg changed things and come up with this variation, which added a nice layer of complexity.

[Guest]

9...

[Guest]

drop the 1st egg from the 16th floor (1st test)

if the 1st egg breaks, 

    drop the 2nd egg from the 5th floor (2nd test)

    if it breaks,

        drop the 3rd egg from the 1st floor (3rd test)

	if it breaks,

	    highest floor = 0

	else

	    drop the 3rd egg from the 2nd floor (4th test)

	    if it breaks,

	        highest floor = 1

	    else 

		drop the 3rd egg from the 3rd floor (5th test)

		if it breaks,

		    highest floor = 2

		else

		    drop the 3rd egg from the 4th floor (6th test)

		    if it breaks,

		        highest floor = 3

		    else

                        highest floor = 4

                    end if

	        end if

            end if

        end if

    else

        drop the 2nd egg from the 9th floor (3rd test)

        if it breaks,

	    drop the 3rd egg from the 6th foor (4th test)

	    if it breaks,

	        highest floor = 5

	    else

	        drop the 3rd egg from the 7th floor (5th test)

	        if it breaks,

                    highest floor = 6

                else

                    drop the 3rd egg from the 8th floor (6th test)

	            if it breaks,

                        highest floor = 7

                    else

                        highest floor = 8

                    end if

                end if

            end if

        else

            drop the 2nd egg from the 12th floor (4th test)

            if it breaks,

                drop the 3rd egg from the 10th floor (5th test)

                if it breaks,

                     highest floor = 9

                else

                    drop the 3rd egg from the 11th floor (6th test)

                    if it breaks,

                        highest floor = 10

                    else

                        highest floor = 11

                    end if

                end if

            else

                drop the 2nd egg from the 14th floor (5th test)

                if it breaks,

                    drop the 3rd egg from the 13th floor (6th test)

                    if it breaks, 

                        highest floor = 12

                    else

                        highest floor = 13

                    end if

                else

                    drop the 3rd egg from the 15th floor (6th test)

                    if it breaks,

                        highest floor = 14

                    else

                        highest floor = 15

                    end if

                end if

            end if            

        end if

    end if

else

    the highest floor = 16+

    even though you may have all 3 eggs at this point to test for higher 

    floors, there was no guarantee the egg would not have broken at the

    16th floor or lower, thus beginning at the 16th floor with 3 eggs to 

    to drop in 6 tests does allow you to cover all possibilities from 

    the 16 floor or lower 

....