• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 12:42
CEST 18:42
KST 01:42
  • 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: Rogue, GuMiho, Solar, Maru0BGE Stara Zagora 2025: Info & Preview27Code S RO12 Preview: GuMiho, Bunny, SHIN, ByuN3The Memories We Share - Facing the Final(?) GSL47Code S RO12 Preview: Cure, Zoun, Solar, Creator4
Community News
Weekly 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-back0EWC 2025 Regional Qualifier Results26
StarCraft 2
General
Code S RO8 Preview: Rogue, GuMiho, Solar, Maru Jim claims he and Firefly were involved in match-fixing The SCII GOAT: A statistical Evaluation StarCraft 1 & 2 Added to Xbox Game Pass CN community: Firefly accused of suspicious activities
Tourneys
Sea Duckling Open (Global, Bronze-Diamond) Bellum Gens Elite: Stara Zagora 2025 $3,500 WardiTV European League 2025 Sparkling Tuna Cup - Weekly Open Tournament SOOPer7s Showmatches 2025
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/ FlaSh Witnesses SCV Pull Off the Impossible vs Shu BW General Discussion StarCraft & BroodWar Campaign Speedrun Quest Will foreigners ever be able to challenge Koreans?
Tourneys
[ASL19] Grand Finals NA Team League 6/8/2025 [Megathread] Daily Proleagues [BSL20] ProLeague Bracket Stage - Day 2
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 What do you want from future RTS games? Armies of Exigo - YesYes? Nintendo Switch Thread Path of Exile
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
LiquidLegends to reintegrate into TL.net
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 Vape Nation Thread European Politico-economics QA Mega-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: 40444 users

Interesting maths problem - Page 3

Blogs > MakkurtE
Post a Reply
Prev 1 2 3 All
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.
Prev 1 2 3 All
Please log in or register to reply.
Live Events Refresh
WardiTV Invitational
11:00
WardiTV June Groups A & 1/2C
Krystianer vs YoungYakovLIVE!
WardiTV1076
IndyStarCraft 275
TKL 117
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
mouzHeroMarine 358
IndyStarCraft 275
TKL 117
ProTech96
BRAT_OK 62
StarCraft: Brood War
Britney 7990
Sea 3235
EffOrt 1226
Stork 655
Mini 534
Snow 458
ggaemo 437
Light 358
ZerO 227
Nal_rA 162
[ Show more ]
actioN 123
Mong 108
sSak 74
Sharp 68
Trikslyr63
Movie 57
Dewaltoss 54
Hyun 46
Sacsri 37
GoRush 29
Aegong 23
Backho 19
Terrorterran 17
Shine 10
yabsab 9
Dota 2
Gorgc11758
syndereN611
Counter-Strike
fl0m5685
olofmeister2892
Stewie2K686
Foxcn318
byalli256
rGuardiaN104
Heroes of the Storm
Khaldor140
Other Games
tarik_tv32065
gofns10872
B2W.Neo1956
singsing1578
FrodaN630
Beastyqt612
Lowko231
crisheroes189
XaKoH 187
Mew2King94
KnowMe80
QueenE59
ZerO(Twitch)23
Organizations
Other Games
BasetradeTV32
StarCraft 2
angryscii 8
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
Dota 2
PGL Dota 2 - Main Stream0
StarCraft: Brood War
sctven
[ Show 18 non-featured ]
StarCraft 2
• poizon28 44
• IndyKCrew
• sooper7s
• AfreecaTV YouTube
• Migwel
• intothetv
• LaughNgamezSOOP
• Kozan
StarCraft: Brood War
• HerbMon 14
• Azhi_Dahaki4
• STPLYoutube
• ZZZeroYoutube
• BSLYoutube
Dota 2
• C_a_k_e 3868
League of Legends
• Nemesis7424
• Jankos1945
• TFBlade1416
Other Games
• Shiphtur224
Upcoming Events
PiGosaur Monday
7h 18m
GSL Code S
16h 48m
Rogue vs GuMiho
Maru vs Solar
Online Event
1d 7h
Replay Cast
1d 9h
GSL Code S
1d 16h
herO vs Zoun
Classic vs Bunny
The PondCast
1d 17h
Replay Cast
2 days
WardiTV Invitational
2 days
OSC
2 days
Korean StarCraft League
3 days
[ Show More ]
CranKy Ducklings
3 days
WardiTV Invitational
3 days
Cheesadelphia
3 days
CSO Cup
4 days
GSL Code S
4 days
Sparkling Tuna Cup
4 days
Replay Cast
5 days
Wardi Open
5 days
Replay Cast
6 days
Replay Cast
6 days
RSL Revival
6 days
Cure vs Percival
ByuN vs Spirit
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.