• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 21:39
CEST 03:39
KST 10:39
  • 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
Code S RO8 Preview: herO, Zoun, Bunny, Classic3Code S RO8 Preview: Rogue, GuMiho, Solar, Maru3BGE Stara Zagora 2025: Info & Preview27Code S RO12 Preview: GuMiho, Bunny, SHIN, ByuN3The Memories We Share - Facing the Final(?) GSL47
Community News
BGE Stara Zagora 2025 - Replay Pack2Weekly Cups (June 2-8): herO doubles down1[BSL20] ProLeague: Bracket Stage & Dates9GSL Ro4 and Finals moved to Sunday June 15th13Weekly Cups (May 27-June 1): ByuN goes back-to-back0
StarCraft 2
General
Code S RO8 Preview: herO, Zoun, Bunny, Classic Jim claims he and Firefly were involved in match-fixing The SCII GOAT: A statistical Evaluation DreamHack Dallas 2025 - Official Replay Pack BGE Stara Zagora 2025 - Replay Pack
Tourneys
[GSL 2025] Code S:Season 2 - RO8 - Group A RSL: Revival, a new crowdfunded tournament series SOOPer7s Showmatches 2025 Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond)
Strategy
[G] Darkgrid Layout Simple Questions Simple Answers [G] PvT Cheese: 13 Gate Proxy Robo
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 477 Slow and Steady Mutation # 476 Charnel House Mutation # 475 Hard Target Mutation # 474 Futile Resistance
Brood War
General
BGH auto balance -> http://bghmmr.eu/ BW General Discussion FlaSh Witnesses SCV Pull Off the Impossible vs Shu StarCraft & BroodWar Campaign Speedrun Quest Will foreigners ever be able to challenge Koreans?
Tourneys
NA Team League 6/8/2025 [ASL19] Grand Finals [BSL20] GosuLeague RO16 - Tue & Wed 20:00+CET [Megathread] Daily Proleagues
Strategy
I am doing this better than progamers do. [G] How to get started on ladder as a new Z player
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Beyond All Reason Path of Exile What do you want from future RTS games?
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Wizard Hilton Cybertech Crypto Recovery: Proven Re
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 UK Politics Mega-thread Russo-Ukrainian War Thread Vape Nation Thread
Fan Clubs
Maru Fan Club Serral Fan Club
Media & Entertainment
Korean Music Discussion [Manga] One Piece
Sports
2024 - 2025 Football Thread Formula 1 Discussion NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
A Better Routine For Progame…
TrAiDoS
StarCraft improvement
iopq
Heero Yuy & the Tax…
KrillinFromwales
I was completely wrong ab…
jameswatts
Need Your Help/Advice
Glider
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 26419 users

Interesting maths problem

Blogs > MakkurtE
Post a Reply
Normal
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
Last Edited: 2009-11-10 16:50:52
November 10 2009 16:49 GMT
#1
So i lurk an awful lot these days and really enjoy the puzzle/maths homework questions that pop up from time to time, so thought i'd share one.

A friend got asked the following during a job interview for an actuarial position:


"Someone gives you two identical and supposedly unbreakable eggs. You have access to a 50 storey building. You want to test whether the eggs are unbreakable or not. What is the minimum number of drops of eggs out of windows to allow you to find the lowest floor (if it exists) that the eggs break on."


I'm pretty sure it's a (relatively) common problem, that you could just google, but it's a nice one to try to figure out.

I'll provide spoilered vague hints if requested



=====



Bonus question:


"You have a large cube, made up of 1000 smaller cubes (10x10x10). You break off the top layer all over the surface of the cube. How many do you have left?"


btw that's a very simple puzzle, but they wanted to see the thought process behind getting to your answer, and asked him to reason it out loud.

*****
Opinions in the above post are less informed then they appear
gumbum8
Profile Blog Joined December 2008
United States721 Posts
November 10 2009 16:57 GMT
#2
+ Show Spoiler +
Well for the first one, I'd say one, because if you start with the top floor and you drop it and it doesn't break, then you know. I feel like that answer is a cop-out though...

And I have to study bio so I'll get back to you on the second one.
but really, has anyone REALLY been far even as decided to use even go want to do look more like?
OreoBoi
Profile Blog Joined December 2008
Canada1639 Posts
Last Edited: 2009-11-10 17:09:16
November 10 2009 16:59 GMT
#3
The second one seems to be 900 ice cubes

edit: whoops i misread the question
so ya its 8 ^3
Sadistx
Profile Blog Joined February 2009
Zimbabwe5568 Posts
November 10 2009 17:01 GMT
#4
"Someone gives you two identical and supposedly unbreakable eggs. You have access to a 50 storey building. You want to test whether the eggs are unbreakable or not. What is the minimum number of drops of eggs out of windows to allow you to find the lowest floor (if it exists) that the eggs break on."


One drop. If they are supposedly unbreakable and one of them breaks, I'll go find the someone who gave them to me and drop them off the 50 story building for being a liar, unless they tell me how tough they really are.

Bonus question - 8^3=512.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 17:03 GMT
#5
I'll reply unspoilered to ya gumbum just to clarify things for everyone else too

Well for the first one, I'd say one, because if you start with the top floor and you drop it and it doesn't break, then you know. I feel like that answer is a cop-out though...


sure, if you drop it off the top and it doesn't break then you did it in one drop, but what if it does? then all you know that it breaks dropped from somewhere between 1 and 50 floors. likewise, you could just get lucky and find the floor on your first try.

the question is at least how many drops do you need to do to always be guaranteed to find the exact floor it will break from.
Opinions in the above post are less informed then they appear
Kiarip
Profile Joined August 2008
United States1835 Posts
Last Edited: 2009-11-10 17:08:09
November 10 2009 17:04 GMT
#6
#1

+ Show Spoiler +
I would say it's 6ish unless gumbum8's answer is actually right...

you start at 25th floor I think, and then if it doesn't break you go up, if it breaks you go down to either 37 or 12, and etc keep dividing stuff in half like binary search or w.e


edit: wtf you only get 2 eggs? OH... I see um... I don't get the question. I mean it could always be one if you mean minimum... but do you mean the minimum in worst case scenario? Then you'd have to throw it like 26ish times.

you throw the first egg off the 25th floor, and then if it breaks, you start dropping the second egg from the first floor and go one up until it breaks, but if ti doesn't break you start dropping it off 26th and up floors one by one until it breaks.


so 26 is the worst case scenario situation I think.



#2


+ Show Spoiler +
Eh well aren't you just left with a 8x8x8 cube? which is 512
Kau *
Profile Joined March 2007
Canada3500 Posts
Last Edited: 2009-11-10 17:08:09
November 10 2009 17:05 GMT
#7
Question 1 is 8? Similar to binary searching?

Question 2 is 1000 - 100 - 100 - 80 - 80 - 64 - 64 = 512

Edit: oh you get two eggs, then you need 26 drops because you can only go two floors at a time.
Moderator
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 17:07 GMT
#8
klarp

#1 - the answers not right. but more importantly - you only have 2 eggs. say you start at 25, and it breaks, and you go up to 37, and it breaks - then you're done. you only have 2 eggs

you will need to do maths to solve it

#2 yeah thats right. it was the logic they were looking for apparently. as in

+ Show Spoiler +
that you realise that you end up with an 8x8x8 cube, instead of just trying to count the cubes you took off
Opinions in the above post are less informed then they appear
illu
Profile Blog Joined December 2008
Canada2531 Posts
Last Edited: 2009-11-10 17:10:39
November 10 2009 17:08 GMT
#9
Since you got only two eggs, the only way to be sure is to take the first egg, and drop it once every three floors, in ascending orders. Say

1 -> 4 -> 7 -> 10 ...

Eventually your first egg will break. Say it happend at 37. Then you drop the other egg at 35th floor to see if it also breaks. If it breaks, then 35th is the lowest floor that will break the egg. If it does not, then try again at 36th.

EDIT: OK I found a problem with my solution. I will fix it later.
:]
Biochemist
Profile Blog Joined February 2009
United States1008 Posts
Last Edited: 2009-11-10 17:09:58
November 10 2009 17:08 GMT
#10
The second one is certainly 512, not 900. It would be 900 if you only took off the first layer on a single side.

I don't get the first one. Maybe there's a shortcut I'm not imagining, but you'd have to start at the 1st floor and go up one at a time. The minimum would be one drop, if they break while dropping them from the first floor. If you started at the top and they broke, you would know that they will break from 50 stories but won't know what the minimum is--hence starting from the bottom.

Edit: Illu is smarter than I am.
Kiarip
Profile Joined August 2008
United States1835 Posts
November 10 2009 17:09 GMT
#11
On November 11 2009 02:07 MakkurtE wrote:
klarp

#1 - the answers not right. but more importantly - you only have 2 eggs. say you start at 25, and it breaks, and you go up to 37, and it breaks - then you're done. you only have 2 eggs

you will need to do maths to solve it

#2 yeah thats right. it was the logic they were looking for apparently. as in

+ Show Spoiler +
that you realise that you end up with an 8x8x8 cube, instead of just trying to count the cubes you took off


got new answer for #1 in my original post!!! check it out
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 17:12 GMT
#12
@illu

that's one way to do it, but theres a far faster way to do it, and also be just as sure. it's not a trick question btw.
Opinions in the above post are less informed then they appear
LiAlH4
Profile Joined October 2007
New Zealand111 Posts
Last Edited: 2009-11-10 17:19:04
November 10 2009 17:14 GMT
#13
+ Show Spoiler +

10 drops I think

+ Show Spoiler +

Start at 10th floor, if it breaks drop second egg from first floor and work up to the 9th.
If it doesn't break, drop from the 19th, 27th, 34th, 40th, 45th, 49th


MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 17:16 GMT
#14
got new answer for #1 in my original post!!! check it out


it's the worst case scenario alright. as in the minimum to be sure of every floor, whether thats the 1st or the 50th. you're getting slightly warmer though, although {your answer] is way too high.


Opinions in the above post are less informed then they appear
OreoBoi
Profile Blog Joined December 2008
Canada1639 Posts
November 10 2009 17:18 GMT
#15
On November 11 2009 02:08 Biochemist wrote:
The second one is certainly 512, not 900. It would be 900 if you only took off the first layer on a single side.

I don't get the first one. Maybe there's a shortcut I'm not imagining, but you'd have to start at the 1st floor and go up one at a time. The minimum would be one drop, if they break while dropping them from the first floor. If you started at the top and they broke, you would know that they will break from 50 stories but won't know what the minimum is--hence starting from the bottom.


Ya I screwed up that question, I'm in class so I wasn't reading the question too carefully X.X
I think the first one the logic is:
- Drop it from the 50th floor
- If it breaks, drop it from the first floor
- If it doesn't break, you have an unbreakable egg
- If it breaks on the 1st floor, the first floor is the lowest floor
- If it doesn't break on the 1st floor, then you drop it from the 25th floor
- If it breaks on the 25th floor, go to the 13th or 12th floor
- If it doesn't break on the 25th floor, go to the 37th or the 38th floor
etc.

Or you could cheat, and you throw it on the ground and it breaks (because it is an egg)
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
Last Edited: 2009-11-10 17:20:06
November 10 2009 17:19 GMT
#16
@LiAIH4
+ Show Spoiler +
gg, took me aaaaaages to work it out. 10 is absolutely optimal. actually optimal is like 9.5 drops when you solve the equations, but you have to round it up obviously


@oreoboi
you only have 2 eggs. once 2 break, you're done
Opinions in the above post are less informed then they appear
Muff2n
Profile Blog Joined March 2009
United Kingdom250 Posts
November 10 2009 17:21 GMT
#17
It would take me 10 drops to be sure.
Dropping in this order (assuming no breakages):
10
19
27
34
40
45
48
Kiarip
Profile Joined August 2008
United States1835 Posts
November 10 2009 17:33 GMT
#18
Alright yeah you get an equation n + (n-1) + (n-2) + (n-3) +... + (n-k) = 50 and (n-k-1) + (n-k) = n

or something like that, you solve and you get approximate answer, then try around there and it turns out to be 10.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 17:39 GMT
#19
solution:

+ Show Spoiler +

x^2 + x - 2(floors)=0 will solve for 2 eggs and any number of floors

in this case optimal is 9.xxxx, but you can't drop an egg 9 and a half times - so 10.

for the answer to be a perfectly round number the number of floors has to be a triangular number

i love the elegance of the method to get to the equation more then anything else really
Opinions in the above post are less informed then they appear
Kiarip
Profile Joined August 2008
United States1835 Posts
November 10 2009 17:58 GMT
#20
mine came out to be way different, but it gave a similar answer in the end =/ Since the approximations aren't exact there'd be a bunch of different equations that solve for this I think.

! Problem:

I remember solving this for so long, and I still dun remember if I actually finished it back when i was in high school:

For all integers 4x^2 + x = 3y^2 + y, prove that y-x is a perfect square.
oBlade
Profile Blog Joined December 2008
United States5483 Posts
November 10 2009 19:33 GMT
#21
#2

+ Show Spoiler +
yeah, 512


#1

+ Show Spoiler +

(don't forget you have just two eggs, so you can't apply binary searching; suppose you take your SUPPOSEDLY unbreakable egg and drop it from the 25th floor, now you have one egg left and no clue what the critical floor is)

drop at floor f and it breaks, so you drop at f-2; if it breaks at f-2, you're done. if it doesn't break, you have to drop at f-1
drop at floor f and it doesn't break, drop at f+3
so you start from floor 3

so if they were unbreakable you would drop all 16 times to get to the 48th floor but because 3 goes into 50 with a remainder , you have to drop again at the 50th floor (if it were to break at the 50th, you would have to use the 18th drop on the 49th floor, but otherwise, it would take 17 drops)

if they are unbreakable, you have to drop 17 times to SAFELY verify that they are unbreakable; if you drop more than this, you're fine, because you would just be doing a linear evaluation like start at floor 1 and go to 50 (if the eggs' integrity isn't affected by the impacts). but if you drop fewer times than this, you get fucked up if they DO break like the people who want to do binary searching.

after you drop at 48, you don't have to drop at 49 before 50 which is why it doesn't take 50/3 + remainder drops (that would be 18)

it takes 17 drops because we don't KNOW that they're unbreakable, if we knew they were unbreakable it would only take 1 drop (at floor 50, but if your egg broke at floor 50, you would have to do a linear search and drop a max of 49 times to safely figure it out). we have to test it as though we didn't know, which is the above method. 17 drops.

"I read it. You know how to read, you ignorant fuck?" - Andy Dufresne
AeTheReal
Profile Joined June 2009
United States108 Posts
Last Edited: 2009-11-10 21:44:49
November 10 2009 20:04 GMT
#22
+ Show Spoiler [Question #1] +
The correct answer for the first problem should be 6. You start on the 25th floor and go up half the floors left if the egg doesn't break. At best case scenario, where the egg breaks only at the 50 floor or doesn't break at all, you would test 6 times.

25, 38, 44, 47, 49, 50

If the egg breaks at any point before the 50th floor, then you would have to start testing from the floor above the last floor that it didn't break from. But yeah, the least number of tests to find the floor which the egg breaks is 6.

Nevermind. Was only thinking about best case scenario.

+ Show Spoiler [Question #2] +
People already got this one. It's 8^3, which is 512.
oBlade
Profile Blog Joined December 2008
United States5483 Posts
November 10 2009 20:15 GMT
#23
Question #1 revisited


+ Show Spoiler +
stop trying to use binary searching. it's tantamount to saying "I know this egg is unbreakable so I will just drop it on the 50th floor so it only takes me 1 drop"

My 17 drop method is in fact not the most efficient (I retract any implications I made to that effect) - although it's miles better than the binary searching bullshit which isn't even valid. I see the 10 drop method now. That's really elegant, and I'm going to remember that.

"I read it. You know how to read, you ignorant fuck?" - Andy Dufresne
Deleted User 3420
Profile Blog Joined May 2003
24492 Posts
Last Edited: 2009-11-10 22:31:44
November 10 2009 20:31 GMT
#24
@LiAIH4

i think ur rightbut ur order for dropping can be improved on. here is what i put

+ Show Spoiler +

10,19,27,34,40,45,48,50,49

or, if it breaks on 10
10,1,2,3,4,5,6,7,8,9




actually, i guess the best way to go would be
10,18,26,33,39,44,47,48,49,50


AeTheReal
Profile Joined June 2009
United States108 Posts
Last Edited: 2009-11-10 21:31:38
November 10 2009 21:23 GMT
#25
Edit: Oops, hit back too much and resubmitted old stuff.
Edit2: Looks like LiAIH4 has the right answer.
gyth
Profile Blog Joined September 2009
657 Posts
November 10 2009 21:44 GMT
#26
For all integers 4x^2 + x = 3y^2 + y


Are there any non zero solutions to that equation?
The plural of anecdote is not data.
Bearigator
Profile Blog Joined July 2009
United States233 Posts
Last Edited: 2009-11-10 21:58:18
November 10 2009 21:55 GMT
#27
Question 1
I think everybody is over complicating this.
+ Show Spoiler +
The answer is 2 drops. That is the minimum number you would need to find out at which floor it would break.

Example: Let us say the egg will break if you drop it off the 30th floor or higher. For your first attempt you just happen to drop it off the 30th floor. For your 2nd attempt, you go down one floor and drop it off the 29th floor. You now know that it will break on the 30th floor but no lower. Problem solved, 2 drops.

Alternatively, if the eggs really are unbreakable, you could figure that out with one drop off the 50th floor. In that case, the answer is 1 drop.

It won't work without fail obviously, but it accurately answers the question as given. Maybe I am that jerk who looks at the wording too hard though, idk.

Question 2
+ Show Spoiler +
512, everybody already posted that one. 8x8x8 == 512
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 22:04 GMT
#28
yes, you're reading it badly. so badly.

It won't work without fail obviously
Opinions in the above post are less informed then they appear
Bearigator
Profile Blog Joined July 2009
United States233 Posts
Last Edited: 2009-11-10 22:32:52
November 10 2009 22:30 GMT
#29
On November 11 2009 07:04 MakkurtE wrote:
yes, you're reading it badly. so badly.

Show nested quote +
It won't work without fail obviously

The question never says it has to work 100% of the time, just the minimum number. Hence my statement that I might just be reading it too literally.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 22:39 GMT
#30
it also never said "if the first floor you randomly choose is the one the above breaking point" but don't let that stop ya

shine on you pedantic diamond
Opinions in the above post are less informed then they appear
conCentrate9
Profile Blog Joined December 2007
United States438 Posts
November 10 2009 22:50 GMT
#31
On November 11 2009 02:39 MakkurtE wrote:
solution:

+ Show Spoiler +

x^2 + x - 2(floors)=0 will solve for 2 eggs and any number of floors

in this case optimal is 9.xxxx, but you can't drop an egg 9 and a half times - so 10.

for the answer to be a perfectly round number the number of floors has to be a triangular number

i love the elegance of the method to get to the equation more then anything else really


Could you explain how you arrived at the equation? I'm not seeing the method.
JeeJee
Profile Blog Joined July 2003
Canada5652 Posts
November 10 2009 22:55 GMT
#32
On November 11 2009 07:39 MakkurtE wrote:
it also never said "if the first floor you randomly choose is the one the above breaking point" but don't let that stop ya

shine on you pedantic diamond


no need to get uppity, makkurte, he's not wrong. the question should have been phrased better.
(\o/)  If you want it, you find a way. Otherwise you find excuses. No exceptions.
 /_\   aka Shinbi (requesting a name change since 27/05/09 ☺)
Bearigator
Profile Blog Joined July 2009
United States233 Posts
Last Edited: 2009-11-10 23:16:32
November 10 2009 23:11 GMT
#33
On November 11 2009 07:39 MakkurtE wrote:
it also never said "if the first floor you randomly choose is the one the above breaking point" but don't let that stop ya

shine on you pedantic diamond

I pointed out why my answer was probably flawed. I was very clear that my answer was just taking advantage of the wording. No need to try to use ridiculous extremes and sarcasm to point out what I already did.

Edit: Also I think your formula will not solve for any number of floors. Edit again after I actually do the math.
Impervious
Profile Blog Joined March 2009
Canada4198 Posts
Last Edited: 2009-11-10 23:15:28
November 10 2009 23:14 GMT
#34
Tried to quote someone and their post was deleted.....
~ \(ˌ)im-ˈpər-vē-əs\ : not capable of being damaged or harmed.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 23:16 GMT
#35
jeejee/bear - thats i know it's awkwardly worded, thats why i clarified it properly, several times. going back and picking at the original statement is pointless and tiresome


and lol, are you kidding me?

x^2 + x - 2(floors) = 0
x^2 + x - 2(10) = 0
x^2 + x - 20 = 0
(x+5)(x-4) = 0
x = -5 x = 4
x = -5 inadmissable

x=4 in the answer
Opinions in the above post are less informed then they appear
Bearigator
Profile Blog Joined July 2009
United States233 Posts
Last Edited: 2009-11-10 23:21:34
November 10 2009 23:18 GMT
#36
On November 11 2009 08:16 MakkurtE wrote:
jeejee/bear - thats i know it's awkwardly worded, thats why i clarified it properly, several times. going back and picking at the original statement is pointless and tiresome


and lol, are you kidding me?

x^2 + x - 2(floors) = 0
x^2 + x - 2(10) = 0
x^2 + x - 20 = 0
(x+5)(x-4) = 0
x = -5 x = 4
x = -5 inadmissable

x=4 in the answer

How would you go about dropping an egg 4 times to solve it 100% of the time? Seriously, not being an annoying ass, I'm doing different combinations of floor drops and I can't find one that works every time in 4.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 23:20 GMT
#37
conCentrate9:

+ Show Spoiler +
if you had infinite number of eggs you'd just binary search, starting at 25 (wiki can explain that better then i can). but obviously with only two eggs thats out.

so you have to pick a large increment, drop the egg, if it doesn't break, you move up by one more increment and try again until it does. once you find the unsafe large increment floor, you then work your way up to that in one's from the last highest "safe" known floor, one at a time.

so

d=number of drops with egg2
(1+d)+(1+(d-1))+(1+(d-2))+.....+1+0 = no floors
let 1+d=x=total number of drops
x+(x-1)+(x-2).....= floors
x(x+1)/2 = floors
x(x+1) = 2(floors)
x(x+1) - 2(floors) = 0
x^2 +x - 2(floors) = 0

hope you see where i'm coming from now.

i never realized typing formulae was such a pain in the ass
Opinions in the above post are less informed then they appear
Impervious
Profile Blog Joined March 2009
Canada4198 Posts
November 10 2009 23:21 GMT
#38
4 - 7 - 9 - 10

If it breaks on 4, start at 1 and go to 3. Max of 4 drops.
If it breaks on 7, start at 5, and go to 6. Max of 4 drops.
If it breaks on 9, start at 8. Max of 4 drops.
If it breaks on 10, you know where it broke.

Easy.
~ \(ˌ)im-ˈpər-vē-əs\ : not capable of being damaged or harmed.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 23:22 GMT
#39
yup
Opinions in the above post are less informed then they appear
Bearigator
Profile Blog Joined July 2009
United States233 Posts
November 10 2009 23:22 GMT
#40
On November 11 2009 08:21 lMPERVlOUS wrote:
4 - 7 - 9 - 10

If it breaks on 4, start at 1 and go to 3. Max of 4 drops.
If it breaks on 7, start at 5, and go to 6. Max of 4 drops.
If it breaks on 9, start at 8. Max of 4 drops.
If it breaks on 10, you know where it broke.

Easy.

Ah, my bad. I even did that combination of drops. I must have counted wrong or something. My bad.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 10 2009 23:24 GMT
#41
you decrease the the number you go up by when an egg doesn't break by one each time, which cancels out the extra drop caused by it not breaking.

wow, now thats a sentence you can justifiyable rip me for how little sense it makes
Opinions in the above post are less informed then they appear
igotmyown
Profile Blog Joined April 2009
United States4291 Posts
November 10 2009 23:46 GMT
#42
1:
+ Show Spoiler +

10+9+8+7+6+5+4+1=50
gzealot
Profile Blog Joined November 2008
Singapore238 Posts
November 11 2009 00:33 GMT
#43
I had the exact same question for my programming homework. It is simply binary searching.

if both eggs are breakable start from half the max height and towards the max floor. Every iteration, divide the search space by two and drop the egg from that floor. Once the first egg breaks, u know the the max floor on which the egg is breakable is in between the last known safe floor and the floor which the egg broke on. then u run a linear search from the last known safe floor to find the actual number.

Or for an amortized best worst-case algorithm, use steps of sqrt(maxfloor) for your first egg, and when the first egg breaks, run linear search on the second egg.


i.e. you have 50 stories, and the egg breaks on 37 floor. Then u would test in this order:
1st egg: 25 -> 37 (oops the egg breaks!)
2nd egg: 26,27,28,29,30,31,32,33,34,35,36,37(breaks, therefore the egg's value is 36)
There isnt any real shortcut to this problem.
MakkurtE
Profile Blog Joined July 2009
United States46 Posts
November 11 2009 00:50 GMT
#44
what if you drop your first egg from 25 and it breaks - you'd have to work your way up from 1 - potentially 25 drops. did you read the theory of how to do it just as well in less then half that number?
Opinions in the above post are less informed then they appear
gzealot
Profile Blog Joined November 2008
Singapore238 Posts
November 11 2009 01:11 GMT
#45
yea well that is the main failing with the binary search. like i said you could try steps of sqrt(max_floor) but i could also say the same if the egg broke on the 43rd floor, binary search could reach that very fast. each algorithm has it best and worse case scenario.
Cloud
Profile Blog Joined November 2004
Sexico5880 Posts
Last Edited: 2009-11-11 03:21:57
November 11 2009 03:20 GMT
#46
Binary search :/ on a problem that you're supposed to solve without pen or paper?

It's an interview question ffs.

Even if you could use pen and paper, you have only 2 eggs. Binary search is way too risky.
BlueLaguna on West, msg for game.
EsX_Raptor
Profile Blog Joined February 2008
United States2801 Posts
November 11 2009 05:59 GMT
#47
#1 = 7
starfries
Profile Blog Joined July 2009
Canada3508 Posts
November 11 2009 07:33 GMT
#48
Wow, my friend interviewed for a similar position and he got the exact same question (#1). Must be a standard interview question or something...
DJ – do you like ramen, Savior? Savior – not really. Bisu – I eat it often. Flash – I’m a maniac! | Foxer Fighting!
2on2
Profile Joined April 2009
United States142 Posts
Last Edited: 2009-11-11 14:46:16
November 11 2009 14:44 GMT
#49
So whats the answer to #1 and the formula?! Im still stuck on whether or not the eggs will break

Imo if your drop @ 50 and it doesnt break..done..but its an egg and it will break @ 1 so...

But its a math problem and Im no genious so I cant be right
Nytefish
Profile Blog Joined December 2007
United Kingdom4282 Posts
Last Edited: 2009-11-11 15:02:58
November 11 2009 15:00 GMT
#50
Well for #1 it seems like you can easily derive the formula if you know it's triangle numbers, but is there a way to show this has to be the optimum (e.g. equispaced drops will always be equal or worse)? Apart from computing it?

I suppose if you only consider the worst case, triangle numbers win out. The way the question is phrased seems to imply that's what you're looking for too.
No I'm never serious.
Hyperionnn
Profile Blog Joined September 2007
Turkey4968 Posts
November 11 2009 16:33 GMT
#51
#1
+ Show Spoiler +
Drop first egg from 10,19,27,34,40,45,49th floor, when your egg broke in floor 34, then drop your 2nd egg starting with 28 and going on, so my answer is 10


#2
+ Show Spoiler +
8^3=512
Kiarip
Profile Joined August 2008
United States1835 Posts
November 13 2009 00:16 GMT
#52
On November 11 2009 06:44 gyth wrote:
Show nested quote +
For all integers 4x^2 + x = 3y^2 + y


Are there any non zero solutions to that equation?


Yeah there are.

for example: (26,30)
gyth
Profile Blog Joined September 2009
657 Posts
November 13 2009 04:28 GMT
#53
I need another envelope, I can only show x has to be even =_=

y^2 = (4y +4x +1)(y -x)
x^2 = (3y +3x +1)(y -x)
The plural of anecdote is not data.
Luddite
Profile Blog Joined April 2007
United States2315 Posts
November 13 2009 05:12 GMT
#54
#1+ Show Spoiler +
25, 38, 44, 47, 49, 50. That's 6 drops, assuming no breaks. If there's a break somewhere, just search in between that range in the same way. i don't know why people are trying to make this so difficult, and saying 10.
Can't believe I'm still here playing this same game
Impervious
Profile Blog Joined March 2009
Canada4198 Posts
November 13 2009 05:41 GMT
#55
On November 13 2009 14:12 Luddite wrote:
#1+ Show Spoiler +
25, 38, 44, 47, 49, 50. That's 6 drops, assuming no breaks. If there's a break somewhere, just search in between that range in the same way. i don't know why people are trying to make this so difficult, and saying 10.


What if it breaks on 25, then breaks on 12/13 (whichever you choose to drop on)? How do you find out what floor it really breaks on then?

You only have 2 eggs to drop. If the first one breaks on 25, you have to do a linear search from 1-24. That's a potential for 25 drops. The 10 drop method will find it in 10 drops or less.
~ \(ˌ)im-ˈpər-vē-əs\ : not capable of being damaged or harmed.
imDerek
Profile Blog Joined August 2007
United States1944 Posts
Last Edited: 2009-11-13 06:55:37
November 13 2009 06:52 GMT
#56
if you have two eggs, then you should drop the first egg in a way such that it only takes roughly sqrt(N) drops to get to floor N, so you can do either f(n) = sqrt(N)*n or f(n) = n^2, the former is better if the answer is close to N, but the latter works better if the answer is small compared to N, so let's say you use the first one, and you broke it at some floor f(k), then you know the answer N' is within f(k-1) < N' <= f(k), so you use the second egg, start from f(k-1)+1, go up by 1 floor each time until you get the right answer. At the worst case (floor 49), this will require 14 drops if we pick f(n) = 7*n (7,14,21,28,35,42,49,43,44,45,46,47,48,49)


This is also generalizable to if you're given an arbitrarily number of eggs E, then the number of drops required is O(N^(1/E))
Least favorite progamers: Leta, Zero, Mind, Shine, free, really <-- newly added
Jonoman92
Profile Blog Joined September 2006
United States9103 Posts
November 13 2009 07:07 GMT
#57
On November 13 2009 15:52 imDerek wrote:
if you have two eggs, then you should drop the first egg in a way such that it only takes roughly sqrt(N) drops to get to floor N, so you can do either f(n) = sqrt(N)*n or f(n) = n^2, the former is better if the answer is close to N, but the latter works better if the answer is small compared to N, so let's say you use the first one, and you broke it at some floor f(k), then you know the answer N' is within f(k-1) < N' <= f(k), so you use the second egg, start from f(k-1)+1, go up by 1 floor each time until you get the right answer. At the worst case (floor 49), this will require 14 drops if we pick f(n) = 7*n (7,14,21,28,35,42,49,43,44,45,46,47,48,49)


This is also generalizable to if you're given an arbitrarily number of eggs E, then the number of drops required is O(N^(1/E))


Well done, that seems right to me.
Normal
Please log in or register to reply.
Live Events Refresh
Online Event
00:00
LATAM SC2 League: Semifinals
CranKy Ducklings83
Liquipedia
GSL
23:00
Replay Cast
Rogue vs GuMiho
Maru vs Solar
PiGStarcraft559
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
PiGStarcraft530
RuFF_SC2 146
Nina 106
CosmosSc2 65
EnDerr 26
StarCraft: Brood War
Britney 20752
Rain 1687
Artosis 827
Icarus 6
Noble 4
Dota 2
ROOTCatZ10
LuMiX1
Counter-Strike
Coldzera 403
Super Smash Bros
hungrybox909
Heroes of the Storm
Khaldor135
Other Games
summit1g13748
shahzam1539
JimRising 402
ViBE233
Maynarde130
ToD77
C9.Mang057
Organizations
Dota 2
PGL Dota 2 - Main Stream5504
Other Games
gamesdonequick1073
BasetradeTV97
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 14 non-featured ]
StarCraft 2
• Berry_CruncH272
• Hupsaiya 71
• davetesta34
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Doublelift5508
Upcoming Events
Replay Cast
21m
GSL Code S
7h 51m
herO vs Zoun
Classic vs Bunny
The PondCast
8h 21m
Replay Cast
22h 21m
WardiTV Invitational
1d 9h
OSC
1d 11h
Korean StarCraft League
2 days
SOOP
2 days
sOs vs Percival
CranKy Ducklings
2 days
WardiTV Invitational
2 days
[ Show More ]
Cheesadelphia
2 days
CSO Cup
2 days
GSL Code S
3 days
Sparkling Tuna Cup
3 days
Replay Cast
3 days
Wardi Open
4 days
Replay Cast
4 days
Replay Cast
5 days
RSL Revival
5 days
Cure vs Percival
ByuN vs Spirit
RSL Revival
6 days
herO vs sOs
Zoun vs Clem
Replay Cast
6 days
Liquipedia Results

Completed

CSL Season 17: Qualifier 2
BGE Stara Zagora 2025
Heroes 10 EU

Ongoing

JPL Season 2
BSL 2v2 Season 3
BSL Season 20
KCM Race Survival 2025 Season 2
NPSL S3
Rose Open S1
CSL 17: 2025 SUMMER
2025 GSL S2
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
CCT Season 2 Global Finals
IEM Melbourne 2025
YaLLa Compass Qatar 2025
PGL Bucharest 2025
BLAST Open Spring 2025

Upcoming

Copa Latinoamericana 4
CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
K-Championship
SEL Season 2 Championship
Esports World Cup 2025
HSC XXVII
Championship of Russia 2025
Murky Cup #2
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.