| Blogs > evanthebouncy! |
|
hasuprotoss
United States4612 Posts
We know that the sum of the first n integers is [n(n+1)]/2, setting this equal to 100 yields us n^2 + n - 200 = 0. Solving this for n gives us 14.65. Then we start at floor 15. If it breaks go to floor 1 and work up. If it doesn't go to 29 (15 + 14) and test. This worst case is 15, which is the best I've seen (hopefully nobody beat me to it!) Flamewheel > me  | ||
rotinegg
United States1719 Posts
On November 13 2011 13:21 flamewheel wrote: 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. + Show Spoiler + you are right. the answer is 14. the point of the question is to normalize the worst case scenario. the way u would formalize the process of finding 14 is using the n(n+1)/2 = 100, which is the equation for the sum of numbers from 1 to n. Since 200 ~= n^2, choose n = 14 which produces n^2 = 196. I didn't do it that way the first time i solved it though; only figured it out after looking at the question after having solved it lol. | ||
|
unichan
United States4223 Posts
On November 13 2011 13:24 darunia wrote: maths is hard i agree, the egg would obviously crack from either the first or second floor, there's your answer | ||
|
Kiarip
United States1835 Posts
| ||
|
galenkan
39 Posts
+ Show Spoiler + The # of tries in a worse case scenario would be 14. If your solution takes more than 14 tries, you should probably revise it | ||
|
rotinegg
United States1719 Posts
On November 13 2011 13:29 Kiarip wrote: We've had this question like 4 times on this site already... and I was so pumped... got city A full of apples. You want to transport 4000 apples to city B, which is 1000 miles away. U got a truck that can carry 1000 apples at any given time, but it also has a squirrel infestation and 1 apple gets eaten per mile driven. What's your strategy to transport the most apples from city A to B? You can drop off apples along the way and they will be there for you to come pick up later, untouched. Go. edit: don't even expect a response if you write something like 'kill the squirrel!' or 'YOU CAN'T SAVE ANY OF THE APPLES!!!@! LOLZ!Q!!!' | ||
|
Complete
United States1864 Posts
worst case 14 | ||
|
hasuprotoss
United States4612 Posts
On November 13 2011 13:32 rotinegg wrote: got city A full of apples. You want to transport 4000 apples to city B, which is 1000 miles away. U got a truck that can carry 1000 apples at any given time, but it also has a squirrel infestation and 1 apple gets eaten per mile driven. What's your strategy to transport the most apples from city A to B? You can drop off apples along the way and they will be there for you to come pick up later, untouched. Go. Hire an exterminator? Came after your edit | ||
|
Ecrilon
501 Posts
| ||
|
THE_DOMINATOR
United States309 Posts
On November 13 2011 13:32 rotinegg wrote: got city A full of apples. You want to transport 4000 apples to city B, which is 1000 miles away. U got a truck that can carry 1000 apples at any given time, but it also has a squirrel infestation and 1 apple gets eaten per mile driven. What's your strategy to transport the most apples from city A to B? You can drop off apples along the way and they will be there for you to come pick up later, untouched. Go. edit: don't even expect a response if you write something like 'kill the squirrel!' or 'YOU CAN'T SAVE ANY OF THE APPLES!!!@! LOLZ!Q!!!' + Show Spoiler + simple solution: go 500 miles drop off 500 go back go to 500 and pick up 500 then got to B (+500) repeat this 8 times and waste 4000 apples (24 trips total) you can optimize this I'm sure ...do you only have 4000 apples? | ||
|
hacklebeast
United States5090 Posts
On November 13 2011 13:32 rotinegg wrote: got city A full of apples. You want to transport 4000 apples to city B, which is 1000 miles away. U got a truck that can carry 1000 apples at any given time, but it also has a squirrel infestation and 1 apple gets eaten per mile driven. What's your strategy to transport the most apples from city A to B? You can drop off apples along the way and they will be there for you to come pick up later, untouched. Go. edit: don't even expect a response if you write something like 'kill the squirrel!' or 'YOU CAN'T SAVE ANY OF THE APPLES!!!@! LOLZ!Q!!!' + Show Spoiler + Move 1000 apples 1 mile, repeat 4 time so 3996 apples are one mile in. Move 1000 apples 1 mile, repeat 4 time so 3992 apples are two miles in. contine this prosses after the first 250 miles you will have lost 1000 apples, so each mile only loses you 3 additional apples. after 583 (250 + the 333 to lose another thousand) you lose only two, and the rest of the way every mile will only lose you 2 apples. 4000-250*4-333*3-417*2=1164 apples remaining. correct? I had seen the op question before, but not this one. edit, fixed | ||
|
darunia
United States139 Posts
On November 13 2011 14:17 hacklebeast wrote: + Show Spoiler + Move 1000 apples 1 mile, repeat 4 time so 3996 apples are one mile in. Move 1000 apples 1 mile, repeat 4 time so 3992 apples are two miles in. contine this prosses after the first 250 miles you will have lost 1000 apples, so each mile only loses you 3 additional apples. after 583 (250 + the 333 to lose another thousand) you lose only two, and the rest of the way every mile will only lose you 2 apples. 4000-250*4-333*3-417*2=1164 apples remaining. correct? I had seen the op question before, but not this one. edit, fixed Do you realize how bad for the environment that is? Your are trading apples for polar bears at that point | ||
|
jjhchsc2
Korea (South)2393 Posts
| ||
|
Monoxide
Canada1190 Posts
| ||
|
hacklebeast
United States5090 Posts
On November 13 2011 14:36 darunia wrote: Do you realize how bad for the environment that is? Your are trading apples for polar bears at that point oh sure it really isn't necessary to go back untill you hit one of the key points + Show Spoiler + 250, 583, 1000 | ||
|
rotinegg
United States1719 Posts
On November 13 2011 14:17 hacklebeast wrote: + Show Spoiler + Move 1000 apples 1 mile, repeat 4 time so 3996 apples are one mile in. Move 1000 apples 1 mile, repeat 4 time so 3992 apples are two miles in. contine this prosses after the first 250 miles you will have lost 1000 apples, so each mile only loses you 3 additional apples. after 583 (250 + the 333 to lose another thousand) you lose only two, and the rest of the way every mile will only lose you 2 apples. 4000-250*4-333*3-417*2=1164 apples remaining. correct? I had seen the op question before, but not this one. edit, fixed Not bad... You got 13 bottles of wine, one of which is poisoned. You got 4 lab rats, which you can test the wine on. Once poisoned, the rat will die after 23 hours 58 minutes + or - 1 minute. You are having guests in 24 hours, and must prepare 12 bottles of un-poisoned wine. What is your strategy of testing out the wine bottles? | ||
|
hp.Shell
United States2527 Posts
The question reads "in which," not "from." Therefore, the 100th floor is the highest floor number in which the egg can be dropped without breaking. | ||
|
hacklebeast
United States5090 Posts
On November 13 2011 15:05 rotinegg wrote: Not bad... You got 13 bottles of wine, one of which is poisoned. You got 4 lab rats, which you can test the wine on. Once poisoned, the rat will die after 23 hours 58 minutes + or - 1 minute. You are having guests in 24 hours, and must prepare 12 bottles of un-poisoned wine. What is your strategy of testing out the wine bottles? + Show Spoiler + rat 1 2 3 4 wine 1 X X X X wine 2 O X X X wine 3 X O X X wine 4 X X O X wine 5 X X X O wine 6 O O X X wine 7 O X O X wine 8 O X X O wine 9 X O O X wine 10 X O X O wine 11 X X O O wine 12 O O O X wine 13 O O X O I could test 3 more wines with this method aww tl messed up my spacing, but I bet you can figure it out | ||
|
hp.Shell
United States2527 Posts
On November 13 2011 15:05 rotinegg wrote: Not bad... You got 13 bottles of wine, one of which is poisoned. You got 4 lab rats, which you can test the wine on. Once poisoned, the rat will die after 23 hours 58 minutes + or - 1 minute. You are having guests in 24 hours, and must prepare 12 bottles of un-poisoned wine. What is your strategy of testing out the wine bottles? Drink all 13 bottles of wine and show up mysteriously dead to the party. | ||
|
Obelisco
Peru1962 Posts
On November 13 2011 15:05 rotinegg wrote: Not bad... You got 13 bottles of wine, one of which is poisoned. You got 4 lab rats, which you can test the wine on. Once poisoned, the rat will die after 23 hours 58 minutes + or - 1 minute. You are having guests in 24 hours, and must prepare 12 bottles of un-poisoned wine. What is your strategy of testing out the wine bottles? alright let me try + Show Spoiler + lets number rats : 1 2 3 4 lets label bottles: ABCDEFGHIJKLM so u follow this, ( you give the rats (number) a drink from each of the bottles) 1-AEFGHI 2-BEHIJK 3-CFHIJL 4-DGIKL then wait and take results. The labeled bottle is poisoned if: none of the rats died: M then (to the left bottle poisoned, to the right rats which died) A:1 B:2 C:3 D:4 E:1,2 F:1,3 G:1,4 H:1,2,3 I:1,2,3,4 J:2,3 K:2,4 L:3,4 edit:aww to slow t.t | ||
| ||
SC Evo League
S2 Championship: Ro16 Day 2
WardiTV Summer Champion…
Playoffs Day 1
ByuN vs herO
MaxPax vs Zoun
Clem vs NightMare
WardiTV1132
Sparkling Tuna Cup
Weekly #103
Solar vs ShoWTimELIVE!
ByuN vs TBD
[ Submit Event ] |
|
|
|
Chat StarLeague
Razz vs Julia
StRyKeR vs ZZZero
Semih vs TBD
Replay Cast
Afreeca Starleague
Queen vs HyuN
EffOrt vs Calm
Wardi Open
RotterdaM Event
Replay Cast
Afreeca Starleague
Rush vs TBD
Jaedong vs Mong
WardiTV Summer Champion…
PiGosaur Monday
Afreeca Starleague
herO vs TBD
Royal vs Barracks
[ Show More ] |
|
|
EPT
