• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 08:04
CEST 14:04
KST 21:04
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall12HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Esports World Cup 2025 - Brackets Revealed12Weekly Cups (July 7-13): Classic continues to roll4Team TLMC #5 - Submission extension3Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7
StarCraft 2
General
RSL Revival patreon money discussion thread Esports World Cup 2025 - Brackets Revealed Who will win EWC 2025? The GOAT ranking of GOAT rankings Weekly Cups (July 7-13): Classic continues to roll
Tourneys
Sea Duckling Open (Global, Bronze-Diamond) FEL Cracov 2025 (July 27) - $8000 live event RSL: Revival, a new crowdfunded tournament series $5,100+ SEL Season 2 Championship (SC: Evo) WardiTV Mondays
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
External Content
Mutation # 482 Wheel of Misfortune Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome
Brood War
General
Flash Announces (and Retracts) Hiatus From ASL BGH Auto Balance -> http://bghmmr.eu/ BW General Discussion Starcraft in widescreen A cwal.gg Extension - Easily keep track of anyone
Tourneys
[Megathread] Daily Proleagues Cosmonarchy Pro Showmatches CSL Xiamen International Invitational [BSL20] Non-Korean Championship 4x BSL + 4x China
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread Stop Killing Games - European Citizens Initiative Summer Games Done Quick 2025! Things Aren’t Peaceful in Palestine
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
[Manga] One Piece Movie Discussion! Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023 2024 - 2025 Football Thread NBA General Discussion NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 798 users

Math Puzzle [num 20]

Blogs > evanthebouncy!
Post a Reply
1 2 3 4 5 6 Next All
evanthebouncy!
Profile Blog Joined June 2006
United States12796 Posts
November 13 2011 03:31 GMT
#1
This one is a classic, but can you do it?

You have 2 identical eggs, and a 100 floor building. You wish to find out the highest floor number in which the egg can be dropped without breaking.
Describe a strategy which you can precisely find that floor number in the fewest drops.


Q&A:

Q:
But, what do you mean "fewest?"
A:
I mean at the worst case. For instance, your strategy might be try fl1, then fl2, then 3 4 5... Under this strategy, the worst that can happen is the egg never breaks, i.e. it can be dropped from over 100 floors, which will take you all 100 drops to find out. So, this strategy takes 100 drops.

Q:
Does the egg crack if dropped repeatidly?
A:
No, egg is good as new as long as it don't break yet.


Again, put answers in spoilers per usual.
Collaborate, have fun!

--evan

Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
hasuprotoss
Profile Blog Joined March 2004
United States4612 Posts
November 13 2011 03:38 GMT
#2
+ Show Spoiler +

I would assume that since you don't want to run out of eggs you would start at floor 2. If it doesn't break, go to floor 4. When you finally get a break, you go down a floor. If that egg doesn't break you are at the floor that is highest without breaking. Otherwise it's the floor underneath you.

Of course, this takes 50 drops, so it's probably suboptimal.
http://www.teamliquid.net/forum/index.php?viewdays=0&show_part=5 <--- Articles Section on TL
Smurphy
Profile Blog Joined November 2010
United States374 Posts
Last Edited: 2011-11-13 03:44:58
November 13 2011 03:41 GMT
#3
+ Show Spoiler +

1. Drop egg on Floor 3. If it doesn't break, jump to 4.
2. If it breaks, drop on floor 2. If no break - done.
3. If it broke on floor 2, done... it's floor 1.
4. Repeat step #1 on floor X + 2 where X is the floor from step #1.

**edit** I guess it is possible that the egg breaks even from floor 1, so this wouldn't work
blabber
Profile Blog Joined June 2007
United States4448 Posts
Last Edited: 2011-11-13 03:44:17
November 13 2011 03:43 GMT
#4
nvm
blabberrrrr
micronesia
Profile Blog Joined July 2006
United States24671 Posts
November 13 2011 03:49 GMT
#5
+ Show Spoiler +
I'd do the first drop on 33 (1/3). If it breaks, go up from 2. If it doesn't break, go to 55 (1/3). If it breaks, go up from 34. If it doesn't break, go up to 70. If it breaks, go up from 56. If it doesn't break, go up to 80. Etc. No idea if it's ideal but I think it's decent XD
ModeratorThere are animal crackers for people and there are people crackers for animals.
MoonBear
Profile Blog Joined November 2010
Straight outta Johto18973 Posts
Last Edited: 2011-11-13 03:54:10
November 13 2011 03:50 GMT
#6
+ Show Spoiler +
Let us define a process A that averages the value of the highest known failure level, and lowest known success value. In the case of non-integer values, round up. We initially start with the assumption an egg dropped from floor 0 will not crack.

Start at the highest level, 100. Drop Egg. If success, end test. If failure, run process A. Return 50 and repeat test at 50.

If failure or success at 50, run Process A again. So if 50 was a success, you go to 75. If it was a failure you go to 25. Repeat this continuously until Process A returns the same value as the floor you are currently on. This is your maximum floor.

This should only require around 8 tries maximum. Too lazy to calculate the expected value and variance of the number of tries for a scenario where each floor has a equal probability of being the successful level. Also, if you consider the probability of success as the floor level increases to be a decreasing function (as common sense would dictate), other methodologies would be more efficient at solving this problem as the expected value would be lower. However, this methodology returns the lowest number of maximum attempts necessary.

If you don't want the assumption an egg at level 0 does not crack, then run at test there first. If it cracks, then no floor exists where the egg will not crack. This brings the maximum number of tests to run to 9, but not a big deal. Still less than 10.
ModeratorA dream. Do you have one that has cursed you like that? Or maybe... a wish?
micronesia
Profile Blog Joined July 2006
United States24671 Posts
November 13 2011 03:52 GMT
#7
On November 13 2011 12:50 MoonBear wrote:
+ Show Spoiler +
Let us define a process A that averages the value of the highest known failure level, and lowest known success value. In the case of non-integer values, round up. We initially start with the assumption an egg dropped from floor 0 will not crack.

Start at the highest level, 100. Drop Egg. If success, end test. If failure, run process A. Return 50 and repeat test at 50.

If failure or success at 50, run Process A again. So if 50 was a success, you go to 75. If it was a failure you go to 25. Repeat this continuously until Process A returns the same value as the floor you are currently on. This is your maximum floor.

This should only require around 8 tries maximum. Too lazy to calculate the expected value and variance of the number of tries for a scenario where each floor has a equal probability of being the successful level.

You will need more than two eggs for this method.
ModeratorThere are animal crackers for people and there are people crackers for animals.
Smurphy
Profile Blog Joined November 2010
United States374 Posts
November 13 2011 03:53 GMT
#8
On November 13 2011 12:50 MoonBear wrote:
+ Show Spoiler +
Let us define a process A that averages the value of the highest known failure level, and lowest known success value. In the case of non-integer values, round up. We initially start with the assumption an egg dropped from floor 0 will not crack.

Start at the highest level, 100. Drop Egg. If success, end test. If failure, run process A. Return 50 and repeat test at 50.

If failure or success at 50, run Process A again. So if 50 was a success, you go to 75. If it was a failure you go to 25. Repeat this continuously until Process A returns the same value as the floor you are currently on. This is your maximum floor.

This should only require around 8 tries maximum. Too lazy to calculate the expected value and variance of the number of tries for a scenario where each floor has a equal probability of being the successful level.

If you don't want the assumption an egg at level 0 does not crack, then run at test there first. If it cracks, then no floor exists where the egg will not crack. This brings the maximum number of tests to run to 9, but not a big deal. Still less than 10.


+ Show Spoiler +
If you drop at 50 and it breaks and then at 25 and it breaks then you start dropping scrambled eggs.
MoonBear
Profile Blog Joined November 2010
Straight outta Johto18973 Posts
Last Edited: 2011-11-13 03:55:52
November 13 2011 03:55 GMT
#9
Oh, my bad. Didn't read the question properly, lol. Need sleep. Assumed infinite eggs.

Then yah, Smurphy/Hasu's method is probably optimal.
ModeratorA dream. Do you have one that has cursed you like that? Or maybe... a wish?
BajaBlood
Profile Joined August 2009
United States205 Posts
November 13 2011 03:57 GMT
#10
On November 13 2011 12:49 micronesia wrote:
+ Show Spoiler +
I'd do the first drop on 33 (1/3). If it breaks, go up from 2. If it doesn't break, go to 55 (1/3). If it breaks, go up from 34. If it doesn't break, go up to 70. If it breaks, go up from 56. If it doesn't break, go up to 80. Etc. No idea if it's ideal but I think it's decent XD


+ Show Spoiler +
I think this is the right idea, but there has to be some way to pick what the correct ratio is to minimize the number of drops needed (I'm assuming you picked 1/3 relatively arbitrarily)
Smurphy
Profile Blog Joined November 2010
United States374 Posts
November 13 2011 03:57 GMT
#11
On November 13 2011 12:55 MoonBear wrote:
Oh, my bad. Didn't read the question properly, lol. Need sleep. Assumed infinite eggs.

Then yah, Smurphy/Hasu's method is probably optimal.


Mine's the same as the one above me and mine is less effective than the one below me.
JDub
Profile Joined December 2010
United States976 Posts
November 13 2011 04:11 GMT
#12
+ Show Spoiler +
Think about it this way: let h be the highest floor you know it won't break at. Let b be the floor for which the first egg breaks. You will need to then start at h+1 and work up to (b-1) with the second egg.

So, you want to minimize the # of drops of the first egg + b-1-(h+1). Assume you employ a strategy where you pick an increment i and drop the first egg at floors I, 2i, 3i, etc. When the first egg breaks, you will then need I-1 drops (at most) for the second egg. The first egg would have to be dropped 100/I times. So, we wish to minimize 100/I + (I-1). A quick check for reasonable values (you could use calculus as well) will show 10 is the ideal increment. Drop the first egg at floors 10,20,30. First egg will be dropped at most 10 times, and second egg dropped at most 9. Notice that if the increment is 7,8,9,11,12,13, the total number of drops necessary in worst case is also 19 (I think).

Sorry, wrote this on my phone so hard to double check this math. I think 19 is the best you can do
THE_DOMINATOR
Profile Blog Joined April 2010
United States309 Posts
November 13 2011 04:14 GMT
#13
+ Show Spoiler +
you drop from 10 if it doesnt break you move up 10 (10-100max 10 drops) then once that egg breaks say at like 20 then you drop from 11 and increment by 1 (11-19, max 9) so you're max number of drops is 19
DOMINATION
hasuprotoss
Profile Blog Joined March 2004
United States4612 Posts
Last Edited: 2011-11-13 04:18:02
November 13 2011 04:15 GMT
#14
Ok, stolen from Micronesia's but I think this is better:
+ Show Spoiler +
Drop from 9th floor. If breaks, start at floor 1, if not go to floor 18. If it breaks, restart at floor 10, if not go to floor 27. Then the worst case scenario is it takes you getting to the 99th floor on testing which is 18 drops, as opposed to the potential 34 from Micronesia.

Also, going to the 10th provides a worst case of 19, and dropping from the 8th is a worst case of 19 as well, so I'm pretty sure the 9 floor steps is optimal. But there may be another method that's more optimal than this.

EDIT** Un-even dropping intervals may be more optimal but I'm not sure how to calculate this (i.e., we start at 20, then move up to say like 37, then 53, etc.).
http://www.teamliquid.net/forum/index.php?viewdays=0&show_part=5 <--- Articles Section on TL
THE_DOMINATOR
Profile Blog Joined April 2010
United States309 Posts
Last Edited: 2011-11-13 04:18:32
November 13 2011 04:16 GMT
#15
On November 13 2011 13:15 hasuprotoss wrote:
Ok, stolen from Micronesia's but I think this is better:
+ Show Spoiler +
Drop from 9th floor. If breaks, start at floor 1, if not go to floor 18. If it breaks, restart at floor 10, if not go to floor 27. Then the worst case scenario is it takes you getting to the 99th floor on testing which is 18 drops, as opposed to the potential 34 from Micronesia.

Also, going to the 10th provides a worst case of 19, and dropping from the 8th is a worst case of 19 as well, so I'm pretty sure the 9 floor steps is optimal. But there may be another method that's more optimal than this.

too late

edit: for both of us...
DOMINATION
darunia
Profile Blog Joined May 2010
United States139 Posts
November 13 2011 04:17 GMT
#16
On November 13 2011 13:11 JDub wrote:
+ Show Spoiler +
Think about it this way: let h be the highest floor you know it won't break at. Let b be the floor for which the first egg breaks. You will need to then start at h+1 and work up to (b-1) with the second egg.

So, you want to minimize the # of drops of the first egg + b-1-(h+1). Assume you employ a strategy where you pick an increment i and drop the first egg at floors I, 2i, 3i, etc. When the first egg breaks, you will then need I-1 drops (at most) for the second egg. The first egg would have to be dropped 100/I times. So, we wish to minimize 100/I + (I-1). A quick check for reasonable values (you could use calculus as well) will show 10 is the ideal increment. Drop the first egg at floors 10,20,30. First egg will be dropped at most 10 times, and second egg dropped at most 9. Notice that if the increment is 7,8,9,11,12,13, the total number of drops necessary in worst case is also 19 (I think).

Sorry, wrote this on my phone so hard to double check this math. I think 19 is the best you can do


Don't increments of 8, 9, 10, 11, 12, and 13 have the same worst case scenario of 19? I haven't found any better than this ^~^
If it sounds good, it is good.
Antoine
Profile Blog Joined May 2010
United States7481 Posts
Last Edited: 2011-11-13 04:26:19
November 13 2011 04:20 GMT
#17
+ Show Spoiler +
drop your first egg at the following floors, in order. if it breaks at 1 go down to the previous one and start incrementing by 1
15
29
42
54
65
75
84
92
100
your max drops are 16. i don't think this is optimal... i tried starting at floor 14 but then you peter out at 95. i'm probably doing math wrong somewhere.
e: flamewheel is better at addition than i
ModeratorFlash Sea Action Snow Midas | TheStC Ret Tyler MC | RIP 우정호
flamewheel
Profile Blog Joined December 2009
FREEAGLELAND26781 Posts
November 13 2011 04:21 GMT
#18
Oh hmm I think I remember reading about something like this a year or so ago...

+ Show Spoiler [My thought process] +
Guess and check since I'm too dumb to prove stuff!

I'm a fan of square roots. Go with every 10 floors. Start from floor 10, and if the egg breaks check linearly up from floor 1 with egg 2. Barring a break on floor 10, go up by 10 at a time. So 10, 20, 30, 40... If egg 1 breaks, go down 9 floors from the multiple of ten you're on, and check upward with egg 2.

Maximum number of steps is 10 + 9 = 19 if the breaking floor is 99.

I dont't this is optimal. Let's see...

15 floors at a time?

15 30 45 60 75 90 100
If egg breaks on 89 then that's 6 + 14 = 20.

Hmm somewhere in between that.
What about 13?

13 26 39 52 65 78 91 100
Breaking at floor 90... 7 + 12 = 19

14 28 42 56 70 84 98 100
Breaking at floor 97 means 6 + 13 = 19 as well

I still don't think this is right. Hmm... maybe a decreasing jump size?

So 10 floors, 9 floors, 8 floors, 7 floors...

Trying with jump size initial equal to 10 is too many 'jumps'.

Maybe 15?

15 29 42 54 65 75 84 92 99 100
Breaking at floor 15 means 1 + 14 = 15
Breaking at floor 29 means 2 + 13 = 15
...
Breaking at floor 99 means 9 + 6 = 15
Breaking at floor 100 means 10

So perhaps initial jump size is max number of tries needed?

Try jump size initial equal to 14 then

14 27 39 50 60 69 77 84 90 95 99 100
@floor 14: 1 + 13 = 14
@floor 27: 2 + 12 = 14
...
@floor 99: 11+3 = 14
@floor 100: 12

Hmm so perhaps it is better to have jump size decrease to close to one when we near floor 100

13 25 36 46 55 63 70 76 81 85 88 90 91
So initial jump size of 13 fails

Seems like 14 looks nice.

+ Show Spoiler [My Solution] +
We will be jumping floors. The first jump is from ground level to floor 14, so a jump size of 14 floors. Decrease jump size by 1 floor after each jump. Therefore, from 14, jump by 13 floors to 27. From there, jump by 12 to 39... So forth and so on. When the egg breaks, start from the floor higher than the last pre-jump floor (so if egg 1 breaks on floor 39, start dropping egg 2 from floor 28). It should take a maximum number of 14 tries.

Using the decreasing jump size method, we find it should only take as many tries as the initial jump size, but only if we can reach 100 before jump size becomes zero. An initial jump size of 13 fails since you only reach 91 floors, and a jump size of 15 takes 15 tries maximum.

I'm a noob and can't do proofs though.
Writerdamn, i was two days from retirement
Complete
Profile Joined October 2009
United States1864 Posts
Last Edited: 2011-11-13 04:23:32
November 13 2011 04:22 GMT
#19
thinking
darunia
Profile Blog Joined May 2010
United States139 Posts
November 13 2011 04:24 GMT
#20
maths is hard
If it sounds good, it is good.
1 2 3 4 5 6 Next All
Please log in or register to reply.
Live Events Refresh
Next event in 3h 56m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Harstem 180
RotterdaM 61
Trikslyr33
StarCraft: Brood War
Sea 27629
BeSt 4779
Mini 1909
Pusan 982
Stork 610
Zeus 352
PianO 301
EffOrt 301
Last 204
Barracks 131
[ Show more ]
ToSsGirL 110
zelot 64
JulyZerg 58
Aegong 37
Rush 32
Sacsri 27
Sharp 27
sSak 22
GoRush 18
Icarus 14
IntoTheRainbow 12
SilentControl 12
Bale 10
scan(afreeca) 9
Hm[arnc] 8
Noble 7
Britney 0
Dota 2
Gorgc7724
singsing2544
XcaliburYe284
Counter-Strike
x6flipin645
sgares338
oskar96
Super Smash Bros
Mew2King145
Other Games
gofns11564
B2W.Neo869
DeMusliM329
Hui .176
Pyrionflax107
ArmadaUGS20
Organizations
Other Games
gamesdonequick3633
StarCraft: Brood War
lovetv 7
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 12 non-featured ]
StarCraft 2
• Berry_CruncH423
• Hinosc 18
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Upcoming Events
uThermal 2v2 Circuit
3h 56m
Replay Cast
11h 56m
The PondCast
21h 56m
OSC
1d
WardiTV European League
1d 3h
Replay Cast
1d 11h
Epic.LAN
1d 23h
CranKy Ducklings
2 days
Epic.LAN
2 days
CSO Contender
3 days
[ Show More ]
BSL20 Non-Korean Champi…
3 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Sparkling Tuna Cup
3 days
Online Event
4 days
BSL20 Non-Korean Champi…
4 days
Bonyth vs Zhanhun
Dewalt vs Mihu
Hawk vs Sziky
Sziky vs QiaoGege
Mihu vs Hawk
Zhanhun vs Dewalt
Fengzi vs Bonyth
Esports World Cup
5 days
ByuN vs Astrea
Lambo vs HeRoMaRinE
Clem vs TBD
Solar vs Zoun
SHIN vs Reynor
Maru vs TriGGeR
herO vs Lancer
Cure vs ShoWTimE
Esports World Cup
6 days
Liquipedia Results

Completed

CSL 17: 2025 SUMMER
RSL Revival: Season 1
Murky Cup #2

Ongoing

JPL Season 2
BSL 2v2 Season 3
Copa Latinoamericana 4
Jiahua Invitational
BSL20 Non-Korean Championship
Championship of Russia 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
RSL Revival: Season 2
SEL Season 2 Championship
uThermal 2v2 Main Event
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.