• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 07:40
CEST 13:40
KST 20:40
  • 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 Week5[ASL19] Finals Recap: Standing Tall10HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7Weekly Cups (June 30 - July 6): Classic Doubles6[BSL20] Non-Korean Championship 4x BSL + 4x China10Flash Announces Hiatus From ASL70
StarCraft 2
General
TL Team Map Contest #4: Winners RSL Revival patreon money discussion thread Esports World Cup 2025 - Final Player Roster Server Blocker RSL Season 1 - Final Week
Tourneys
$5,100+ SEL Season 2 Championship (SC: Evo) RSL: Revival, a new crowdfunded tournament series $25,000 Streamerzone StarCraft Pro Series announced FEL Cracov 2025 (July 27) - $8000 live event Sparkling Tuna Cup - Weekly Open Tournament
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
External Content
Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma
Brood War
General
Script to open stream directly using middle click A cwal.gg Extension - Easily keep track of anyone BW General Discussion ASL20 Preliminary Maps BGH Auto Balance -> http://bghmmr.eu/
Tourneys
[Megathread] Daily Proleagues Small VOD Thread 2.0 Last Minute Live-Report Thread Resource! [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 Path of Exile CCLP - Command & Conquer League Project The PlayStation 5 Nintendo Switch Thread
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 Things Aren’t Peaceful in Palestine Russo-Ukrainian War Thread The Accidental Video Game Porn Archive Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
2024 - 2025 Football Thread Formula 1 Discussion NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 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: 724 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 States24670 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 States24670 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
RSL Revival
10:00
Season 1: Playoffs Day 7
Cure vs ClemLIVE!
Crank 1425
Tasteless1336
ComeBackTV 1181
IndyStarCraft 224
3DClanTV 84
Rex80
IntoTheiNu 27
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Crank 1425
Tasteless 1336
mouzHeroMarine 394
IndyStarCraft 224
Nina 133
Rex 80
StarCraft: Brood War
Jaedong 1136
Nal_rA 592
ToSsGirL 460
firebathero 338
Light 263
Mini 220
JulyZerg 212
Last 201
PianO 184
EffOrt 174
[ Show more ]
Stork 132
Leta 125
soO 122
Pusan 92
Mind 90
sSak 56
sorry 29
Barracks 27
Shinee 27
zelot 25
Icarus 18
Movie 10
SilentControl 7
ivOry 4
Dota 2
XcaliburYe456
Counter-Strike
chrisJcsgo149
Heroes of the Storm
Khaldor211
Other Games
gofns29524
tarik_tv27450
FrodaN3234
B2W.Neo1231
shahzam408
crisheroes353
DeMusliM348
Fuzer 301
KnowMe171
SortOf137
Lowko114
ArmadaUGS52
Trikslyr27
Organizations
Other Games
gamesdonequick32405
StarCraft: Brood War
CasterMuse 31
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 10 non-featured ]
StarCraft 2
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Upcoming Events
FEL
20m
FEL
4h 20m
Gerald vs PAPI
Spirit vs ArT
CSO Cup
4h 20m
BSL20 Non-Korean Champi…
6h 20m
Bonyth vs QiaoGege
Dewalt vs Fengzi
Hawk vs Zhanhun
Sziky vs Mihu
Mihu vs QiaoGege
Zhanhun vs Sziky
Fengzi vs Hawk
DaveTesta Events
6h 20m
Sparkling Tuna Cup
22h 20m
RSL Revival
22h 20m
Classic vs TBD
FEL
1d 3h
BSL20 Non-Korean Champi…
1d 6h
Bonyth vs Dewalt
QiaoGege vs Dewalt
Hawk vs Bonyth
Sziky vs Fengzi
Mihu vs Zhanhun
QiaoGege vs Zhanhun
Fengzi vs Mihu
Wardi Open
1d 23h
[ Show More ]
Replay Cast
2 days
WardiTV European League
3 days
PiGosaur Monday
3 days
uThermal 2v2 Circuit
4 days
Replay Cast
4 days
The PondCast
4 days
Replay Cast
5 days
Epic.LAN
6 days
CranKy Ducklings
6 days
Liquipedia Results

Completed

KCM Race Survival 2025 Season 2
HSC XXVII
NC Random Cup

Ongoing

JPL Season 2
BSL 2v2 Season 3
Acropolis #3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
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 Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
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
FISSURE Playground #1
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.