/sci/ - Science & Math

>>9882253
I do not, but I am interested.

#1 is simple binary search. Drop an egg at floor 50, if it breaks drop an egg at floor 25, if it does not drop one at 75. Just keep this pattern until you find it using n/2 rounding up, where n is the number of uneliminated floors.

>>9882253
t. comp sci freshman who thinks he's special

>>9882264
But you only have two eggs

>>9882265
Don't be worried buddy, lots of special kids end up in that major.

1. Hatch the eggs and feed the chickens, find a rooster to produce more eggs. Using a now limitless supply of eggs, do >>9882264

>>9882271
YOU ONLY HAVE 2 EGGS

>>9882273
i go to the store and buy all the eggs i want motherfucker

>>9882273
Purchase some chickens from the farmers market.

>>9882268
Don’t be fucking dumb anon. If it doesn’t break you still have two eggs.

How is a local minimum in a grid defined?

>>9882273
No it says you have two eggs, it doesn't say u cant get more by hatching the eggs u have into chickens. This is why u comp sci ppl are losers, u dont think outside box

>>9882278
>if it breaks
>drop an egg at floor 25
>it breaks
congrats you lost both eggs

the eggs will break even on the ground floor. you need 0 drops to determine that. solved

>>9882284
false, the eggs were hard boiled

>>9882287
hard boiled eggs will crack open even on the ground floor

>>9882284
You have to show it experimentally.

>>9882289
false, the building is actually a scaled down model used for building planning

>>9882283
Well if you were dumb enough to drop from floor 25 first and the egg broke, you would simply use the second egg, starting at floor one and working up to 25, and drop it until it broke. Then you have an answer you fucking brainlet. Stop talking you’re too fucking dumb.

>>9882295
you can do better

>>9882296
Wasn’t my idea to start at floor 25 dumb fuck. I would start at 14. Another fucking genius we’ve got here.

>make scrambled eggs on the ground floor
>100% accurate result: the eggs broke on the first floor
>enjoy eggs

>>9882298
>I would start at 14.
h-how did you know

>>9882295
>drop from 50
>it breaks
>drop from 25
>it breaks
>oops

>>9882301
Start at floor n. Next n-1, n-2, so on. n+ (n-1) + (n-2) + (n-3) + ... + 1 <= 100, because we have 100 floors. n is about 14. The fucking state of /sci/

>>9882295
delete this so people don't mock you for your piss-poor reading comprehension and overconfidence.

>>9882311
very nice. you're legit high IQ or decently educated for being able to solve it this quickly.

>>9882311
>=

>>9882314
>has correct answer
>overconfidence
Go away brainlet

>>9882278
nice bait faggot.

Well the best I can come up with is to search every 3 floors... if it breaks on floor n then use your second egg on floor n-2. If that egg breaks you have your answer otherwise try the egg on n-1 if it breaks there you have your answer. If that doesn't break then the answer was n.

Is there a better way? Now I'm curious.

>>9882318
it's famous

>>9882320
first you can try to check every n floors with different n
then do bigger jumps at the beginning to even out the best/worst case scenarios

>>9882321
And therefor shouldn’t be this difficult for all of you /sci/ fags. But here we are, arguing over it for some reason.

not doing your homework, faggot

>>9882320
Start at n. Go to n+(n-1)... rinse repeat

>>9882324
You start on floor 4... it breaks

now there are 3 other possible floors it could break at and you can't do this with only 1 egg

>>9882330
check floor 1, 2, 3 in that order
the lowest floor where the egg breaks is the floor you're looking for

>>9882328
start at 4 it breaks
4+(4-1) = 7 but what good is that?

>>9882253
can I drop it from floor zero?

>>9882330
You could, just not the most efficient way. If it breaks at 4 you drop again at 1 then 2 then 3... fucking think anon.

>>9882336
if it breaks at 4 you check the ones below, if it doesn't break you go to 7

>>9882340
Also seems valid, but none of you fucks have proved that it is optimal

>>9882344
proven right here>>9882298

>>9882336
It’s decreasing the number of inbeween drops you need to make... it didn’t break on 4 so you go to 7 and it breaks, you now only have 2 floors to check. It doesn’t break on 7 so you go to 9 and it breaks. Now you only have one in between floor to check. You see?

>>9882328
>>9882311
>>9882316
n = 100
n + n-1 = 199

You're now free falling 90 stories with the egg.

Fucking idiots everywhere

>>9882341
breaks at 4...
now try 1 2 and breaks at 3...
you just did 4 egg drops

My method:
Start at floor 3... it breaks then try floor 1 then 2
you did 3 total egg drops

So in this case going 3 floors at a time is better

>>9882344
if the first egg breaks you're reduced to having to check floors one by one starting from the highest known safe floor + 1

then by spacing your first-egg tries like in >>9882311 >>9882316 there is no waste in terms of minimizing the max number of floors you need to check

>>9882352
Uh what? If it breaks at 4 and you try 3 after you have not proved it doesn’t break on 1 or 2 brainlet.

>>9882352
you don't know which floor it breaks on. you want to optimize it with the worst case in mind.

>>9882361
Start at 3, it doesn't break go to 6 is breaks
Now try 4 it breaks.

3 TOTAL EGG DROPS FAGGOT

Show me a method thats better than this! PROVE IT

>Start at floor 1
>Drop egg
>It doesn't break
>Go outside and pick the egg back up
>Go to floor 2 and repeat
Shit you guys, I only need one egg to figure this out

>>9882368
Already did up here >>9882311
Faggot.

>>9882385
>smallest number of egg drops

>>9882397
Only one did.

>>9882385
It’s about number of drops brainlet.

so is adding that you only have two eggs in the question for the purpose of making this unsolvable from one angle or another? if you do the most efficient route for drops, somebody mentions “only two eggs”, if you go to preserve your eggs, “most efficient drops.”
t.brainlet

>>9882401
>the problem is easy but you have to change it into a simpler problem first lmao

>>9882417
Did you not learn D&Q?

alternate solution
>>>/g/66819189

>>9882416
the answer is somewhere in between

So whats the most efficient solution given k floors and n eggs?

>>9882264
>at or above a ceetian floor
>not a random floor
>breaks at 50
>doesn't break at 25
>proceeds to drop one at 75
nice logic

>>9882335
This is correct.

Can someone please please explain this whole thing to a brainlet (me); ive read every post in this thread and I still don't get it..

>>9882253
>How should you find this floor with smallest number of egg drops?
Well, that depends on the actual minimum floor number. Do you want the strategy with the smallest *expected* number of drops (over what distribution)? The smallest *worst case* number of drops? Something else?

>>9882829
the smallest worst case number of drops

>>9882824
>2 eggs
>1 building with 100 floors
>at and above a certain floor (the floor you want to find) the eggs will break if you drop them from that floor, meaning you only have 2 tries if you break them since you only have 2 eggs
>but at lower floors the eggs will survive and you can drop them again
>try to come up with a way of finding the first floor that the eggs start breaking at, using the lowest total number of egg drops

>>9882253
Eggs are pretty weak, they should easily break at first floor.

>>9882873
there are thick bushes at the bottom

>>9882253
Assume you already used an egg.
What is the strategy for 1 egg?
Find a strategy for the first egg given that you know the strategy for the second egg.

>>9882742
Find the lowest n such that 1+2+...+n >= k
Then check n, n+n-1, n+n-1+n-2, ...

>>9882742
>>9882923
Wait I'm an idiot and didn't read the question.
The solution approach generalises though.
What you have to do with one egg is forced, so that gives you a best approach for the second egg and so on.

>>9882928
how would you do it with 3 eggs?

>>9882931
eat one.

>>9882271
Can't hatch an egg retard unless it was already fertilised.

Does anyone have an analytical solution to #3? I was bored so I did it in MATLAB and got an answer around ~3.6% but I might be a brainlet.

for i = 1:10000

> % Initialize System

num_red = 80;
urn = zeros(1,100);
urn(1:num_red) = 1;

> % Do an event

while length(urn) > 1
n1 = randi(length(urn));
if urn(n1) == 1
urn(n1) = [];
elseif urn(n1) == 0
n2 = randi(length(urn));
urn(n2) = [];
end
end
store(i) = urn;
end

> % Stats
count = 0;
for i = 1:length(store)
if store(i) == 1
count = count + 1;
end
end
prob_red = count / length(store)

>>9882253
Question 1 is easy as fuck
>Drop an egg from the 2nd floor
>If it breaks stop there
>If it doesn't break go down to the first floor and get your egg
>Go to third floor and drop the egg
>If it doesn't break go down to the first floor and get your egg
repeat until the egg breaks. Guaranteed to lose at least one egg no matter what you do, this method guarantees you only lose one.

>>9882253
Start at the third floor and work your way up in multiples of three. When your first egg breaks, drop the second from one floor lower.

Also, an egg will always break when you drop it from meter height

>>9882311
this does not make sense

>>9883158
see pic in >>9882316
if the first egg breaks from floor 14, you check 1-13 with the second egg
if the first egg survives the drop from floor 14, but breaks from floor 27, you check 15-26 with the second egg
and so on

I don't get the n-1 part. Why not just always drop it in intervals of 14?

>>9882253
#1 gets spammed on /g/ all the time. It baits you into thinking >>9882264 which is a retarded idea. Reminder, after egg 1 breaks you have to go floor by floor with the second one starting at the highest floor the first egg didn't break on. So if it breaks at 50, you have to check from floor 1, one by one.

>>9883203
Think

>>9883203
If it breaks on floor 84, you have done 6 drops and have to do 13 more (starting from 71). 19 drops total. If it breaks on floor 14, you have to do 13 more, which yields 14 total. So in order to account for that you don't space the drops evenly, doing more frequent drops the higher you are.
>inb4 fencepost error
Fuck it, too tired to think about them

>>9883024
Consider learning some reading comprehension retard

>>9882311

>>9883024
> How would you find this floor with the smallest number of eggs drops?
>egg drops
You seem to have read "egg breaks" instead. It's okay. It happens

>>9882931
The best possible worst case solution for any interval (a safe lower and unsafe/maximal upper) with two eggs is m steps, where m is the smallest natural number such that 1+...+m is greater than or equal to the distance of the interval (might be m-1, can't be bothered checking).

To find the solution for two eggs you choose the biggest intervals with decreasing 1 egg score possible (it can be reasoned that this is optimal since if at any step you choose a bigger interval there is a worse worst case).

We do the same thing for the three egg case. The maximal 2 egg intervals are of the form 1+...+x or x(x+1)/2.
We work out the minimum m such that the sum of first m maximal 2 egg intervals (1, 3, 6, 10,...,m(m+1)/2) are greater than the number of floors. We try floor m(m+1)/2. If the egg breaks then we solve it in some amount. If we had instead tried a lower floor then we wouldn't make any difference to the worst case unless we were in a lower maximal interval (in which case we would run into problems later on). If we tried a higher floor then because we would be in a different interval the two egg case worst case would be worse. If the egg doesn't break we go up by the immediately smaller maximal 2 egg interval. It costs us one more egg to get here but if we have a breakage then the worst possible 2 egg case is one better. We then repeat this process all the way.

In the general case of n eggs we just need to calculate maximal intervals for 1,...,n-1 eggs recursively as I described for 3. Sorry if my explanation is unclear. I didn't really provide proof but it should be obvious from thinking about the two egg case. There's also probably a (semi) closed form solution rather than a recursive one.

>>9883161
What makes 14 special though? What makes that number picture special? Why not just use the same method in sets of 10 instead?

>>9883399
The idea is that you decrease the number of floors you are adding on each time.

First floor 14
no break
Now floor 27 (14+13)
no break
Now floor 39 (14+13+12)

Since you took two extra jumps to get to 39 instead of 14, the increment inbetween should be 2 less (14-2=12).
The worst case scenario of maximum egg drops is minimized to 14.

Why 14 as opposed to any random number?

n+(n-1)+(n-2) <=100 for n =14

>>9883399
Notice his step size decreases by one each time he goes up, so with the first egg he's checking floors 14, 14+13, 14+13+12, etc.
If the egg breaks on floor 14 you have to check 1, 2, 3, ..., 13 in order (or risk breaking the second egg without finding the right floor,) which takes 13 drops plus 1 for the initial drop at 14. If it breaks at 27, you'd have to check 15, 16, 17, ..., 26 (12 drops plus one for floor 14 and one for floor 27.) By decrementing the interval size by one for each drop of the first egg, you ensure that regardless of where the first egg breaks you don't need more than 14 total drops to find the right floor. Keeping the same interval size is not optimal because it increases the number of total drops required for each time the first egg doesn't break (i.e. in a worst case.)
Try it out with initial interval widths of 13 and 15 and see what happens. The total worst case number of drops is whichever is greater between 1. the initial interval width and 2. the number of intervals ending below 100 plus the difference between 99 and the last interval's endpoint.

I don't actually know if 14 is the optimal answer because I haven't seen a proof from anyone, but that's the problem as I understand it.

>>9883484
>Why 14 as opposed to any random number?
>n+(n-1)+(n-2) <=100 for n =14
n+(n-1)+(n-2) <=100 for n=1, 2, 3, ..., 33, 34. This doesn't justify anything. Stop being deliberately obtuse.

>>9883495
Thats not true lmao. I may not have been clear enough.

n+(n-1)+(n-2)....+1=100

34+33+32+...+1 is going to be way bigger than 100

>>9883502
You should probably write what you mean on /sci/.
n+(n-1)+(n-2)+...1 <=100 is true for n=1, 2, 3, ..., 14. Keep trying.

>>9883525
Meant 13, not 14

Do a reverse binary search. Start at floor 1 then 2 then 4 then 8...after it cracks go one by one before the first one it cracked fir

>>9883486
intuitive explanation

>>9883495
So this is the absolute state of /sci/

>>9882264
>>9882278
>>9882295
>>9882298
>>9882318
The stupid is incredibly strong here.
>>9882396
That is not a proof, you need to show that the expectation value of drops is less than his or something, assuming a uniform distribution of break floor.

>>9883382
>>9883486
Adding text doesn't legitimize your answer, you haven't come close to showing it's optimal or even compared it to other answers. I don't even see how it would be true intuitively.

If you want to be real pedantic about it, for #1 you need to define what your belief about the distribution of the break floor is, then evaluate your strat in terms of the expected number of drops.

>>9883699
So, we have the three floor drop, so you do floors 3n, the chance it's in any interval is 3/100 and number of egg drops required to find the floor for any interval n is n+1. This is because you use n drops to break the first egg, then the next drop will tell you which floor it is. You can go up to n=33 which is floor 99, and if it breaks there you know it's 100. So, expectation value is
[math]\frac{3}{100}\sum_{n=1}^33(n+1)+\frac{33}{100}=\frac{3\cdot (\frac{34\cdot35}{2}-1)+33}{100}\approx 18,15[/math]
which means that the average number of drops is 18,15, which is the number to beat. I'll try to look at the 14 drop thing, but it's so convoluted that I doubt I'll get through it.

>>9883731
This is like the most naive answer but its still better than anything the other retards on this thread came up with

>>9882264
You only have two eggs, that method requires at most 6 eggs

>>9882253
Buy more eggs you fucking retard

>>9883731
The 14 floor decremental drop:
For the first 13 floors it's m+1 drops, if it's the first floor you do 14 and 1, if it breaks both times, it's 1, else continue. So we get ((14*15)/2-1+14)/100=1,18
For floors 15 to 27 it's the same with an extra drop, so we get 3+4+5+6+7+8+9+10+11+12+13+14+14
which is ((14*15)/2-3+14)/100=1,16
now I'm going to cut corners and assume for interval n that it's (14*17-n*(n+1))/200.
You need to do this for n=4 to 14 which amounts to
[math]\frac{11\cdot14\cdot17-\sum_{n=4}^14n\cdot(n+1))}{200}\approx8,64 drops.[/math]
which means it takes 8,64 drops on average to find the floor, which makes sense since the maximum amount of drops is 14 for any level.

Wait shouldnt the answer be to just drop eggs from each floor from top to bottom untill 1 egg breaks and assume that the next floor will be the "certain" floor? Since theres only 1 certain floor theres no reason for the eggs to break as long as they arent "on" or "above" the "certain" floor :/ impossible to find the "certain floor" by losing 0 eggs, 1 egg must be lost

>>9883792
But optimally you would lose both eggs, or you're not using your tools to their fullest. Even every other floor is better than your method and probably cuts the average in half, and every third floor also works and cuts it even further.

>>9882253
Jesus, what morons.

1. Drop first egg at floor 2.
2. If the first egg breaks, try the second egg at floor 1.
3. If the second egg breaks, end program.
4. If the second egg survives, drop the first egg at floor 4.

Rinse and repeat, going up 2 floors each time.

>>9883801
But it increases the risk of failing to find the floor, youll have 50% chance of finding out whether the true floor is the one on which u are or if its the one immediately below or above

Eat eggs and ask for a bigger research grant

>>9883792
>smallest number of egg drops
Please refrain from answering if your IQ is below 100, thx.

>>9883943
my nibba

>>9883831
Please refer to >>9883951
before any further posting

For all the geniuses who know why the answer is 14, what would be the answer if the building had 150 floors? 200? The general case?

>>9883693
>>9883703
>>9883731
>expectation value
>>>/pol/

>>9882253
Question 3 is the easiest: the answer is 0% since there will always be at least one blue ball in the urn until all are gone. But you knew that.

>>9884172
where did you learn to read?

>>9882253
It's obviously floor 1. You can drop an egg from just a couple feet and it will break.

>>9882253
haha my ex gf asked me this question, she was a comp sci grad who made 250k outta college but thoguht iw as the smartest person on earth.

i studied physics so i kept talking about shit like terminal velocity and stuff it was funny.

fast forward 2 years and i'm making GANs for neural circuits

>>9883699
after the first egg drops, you have to check floors one by one from the highest known safe floor. because of this the only viable strategy to optimize the number of total drops is to have some variation of dropping the first egg from different floors until it breaks and then using the second egg to check floors one by one.

if you use even spacing, such as steps of 10, this is pretty efficient but you can do better because you use fewer drops if the target floor is low and more drops if the target floor is high. by spacing out the drops so each successive drop is from floor n, n+n-1, n+n-1+n-2, n+n-1+n-2+n-3 and so on, you have the same max total number of drops regardless of where the first egg lands, and n is simply the smallest number that will take you to the top floor while using the described pattern.

>>9883821
are you autistic? if you proved it broke on floor 2 why drop on floor 4? Like wtf are you even talking about brainlet

>>9883821
>egg breaks on floor 2
>drop the egg on floor 4

ok this is epic

>>9884537
>his “proof” is 95% English

>>9884599
>this is bait
at least it's an intuitive explanation if you're not an idiot

>>9884607
>>9884537
Not once in this thread has someone showed a step-by-step process of how the pattern n + n-1 + n-2...arises. It’s
all,”Oh yeah, that works, let’s show everyone else that it conveniently works without actually proving it.” Could you prove that there is no better solution without brute forcing all other methods?

>>9882253
Start at floor 1. If it doesn't break, you still have two eggs. Move up one floor at a time until one breaks.

Just start at the second bottom floor and move up floors by two until you get to a floor the egg breaks then use the other egg on the floor one lower than it to determine if it breaks there or the one above it.

>>9882253
what does it mean by smallest number of egg drops? Best case scenario? Worst case scenario? Average number of egg drops?

>>9884619
it's dead simple, jeez, if it breaks at 14 you have up to 13 below it to try (14 drops in total), if it survives at 14 you don't try 28 because then you would have 15-27 to try and your total number of drops would be higher than 14, which is not the goal, you drop it at 27 instead, that's how the pattern arises

>>9884676
worst case

>>9884681
>if it survives at 14 you don't try 28 because then you would have 15-27 to try and your total number of drops would be higher than 14, which is not the goal
>which is not the goal
This makes no sense. Our only goal is to find the floor with the smallest number of egg drops. You pulled the pattern out of your ass, and much worse, without mathematically proving it. Prove that there doesn’t exist some other pattern that that is as good as or better than yours.

>>9884693
see >>9882431 for an alternate solution, but it's obvious that 14 is drops is the best you can do for 2 eggs and 100 floors, a proof doesn't have to convince retards to count as a proof

>>9884697
Let’s say the building has 200 floors. Prove to me first that the pattern is optimal, then find the first floor to drop an egg. If you can’t explain it to a retard, then there is a gap in your comprehension, or you have poor explanation skills.

>>9884711
i've already shown why the pattern is optimal. if you skip ahead more than n-1, you start using more drops, so you could have used a larger n to begin with. if you skip ahead less than n-1, you start using fewer drops, when you could have reached a higher floor without using more drops. take a moment to try to understand it and perhaps work through a few examples if you're not trolling.

>>9884711
has anyone generalized it with n eggs and m floors?

>>9884724
>you start using more drops
more drops than what? n? Why is it that n is both the floor and the max number of drops?

>>9884729
you need to find the exact floor that is high enough for the eggs to break. since you have 2 eggs you can "skip ahead" and see if the first egg will survive a drop from floor n. if the first egg breaks at floor n, you need to check floors 1 through n-1 to find the exact floor. you can't skip ahead with the second egg in case it breaks prematurely.

since the goal is to minimize the total number of drops needed to find the floor, then for the next step if the first egg survives the initial drop from floor n, you subtract one from the remaining number of drops you have to work with (for the optimal solution), because you already used up one drop from floor n.

for example, if the first egg survives the drop from floor n and it breaks from floor 2n, you need to check floors n+1 through 2n-1, so in total you would check n through 2n which is n+1 drops, so the first drop might as well have been from floor n+1 without being any worse of a solution (actually a better solution in terms of reaching to a higher floor in the same worst case number of egg drops)

>>9882301
you could start at floor 9, 10, 11, 12, or 13 and youd still find it in 14 drops

100 <= the 14th triangle number, which is 105.

9+13+12+11 .... +2+1 is still >= 100 so your fine

>>9884724
how can you approach this with 3 eggs? Im too much of a brainlet to generalize it to more eggs

>>9884780
use tetrahedronal numbers lol. hope you know your simplexes

Let f[n] be the floor of your nth egg drop. Let x be the lowest floor at which the egg breaks. Once f[k] >= x then your first egg breaks and you only have one egg left, so you must start at f[k-1]+1 and increment by 1 floor until your egg breaks or you come back to f[k]. This means the amount of total egg drops will be

k + x - f[k-1] if f[k] > x
k + x - f[k-1] - 1 if f[k] = x

This is greatest when x is maximized

k + f[k] - 1 - f[k-1] if f[k] -1 = x
k + f[k] - f[k-1] - 1 if f[k] = x

So the maximum amount of egg drops is always k + f[k] - f[k-1] - 1

When k = 1 the max amount of egg drops is 1 + f[1] - 0 - 1 = f[1]

So the max egg drops for k = 1 is the same as the number of the first floor you start testing. In order to minimize the maximum, we want to keep this the maximum amount for all k.

k + f[k] - f[k-1] - 1 = f[1]
f[k] - f[k-1] = f[1] - k + 1

So the distance between floors decreases by 1 with each egg drop. If 100 <= n(n+1)/2 then n >= 13.651 and the lowest value for f[1] is 14

>>9884780
for the first drop, skip ahead the maximum number of floors you can solve with 2 eggs in n drops, then if the egg survives, skip ahead the maximum number of floors you can solve with 2 eggs in n-1 drops, and so on. then find the lowest n that will get you to the top floor of the building using this pattern.

>>9883204
So then what's the answer genius?

>>9884172

> Two balls left, blue and red
> Draw blue
> put back
> draw same blue
> discard

>>9884843
whats the quickest way of actually computing n? Is there an easy way to do it like with 2 eggs and triangle numbers?

>>9882253
Binary search until the first egg breaks, then linear search starting with the low floor.

Next.

>>9884935
Yeah buddy drop your first egg from floor 50. Maybe it won't break.

>>9884938
Yeah.

>>9884935
lmao this isnt even that hard of a problem. Its like it was specifically constructed to expose CS people and /g/ as brainlets

>>9884941
How is my answer not correct?

>>9884942
>egg breaks at floor 50
>drop second egg 48 times to find the floor

>>9884942
it's far from optimal

>>9884944
>>egg breaks at floor 50
How do you know that?

>>9884946
It's logarithmic until the first egg breaks, it's the best you can do.

>>9884950
its the worst case scenario

>>9884619
>step-by-step process
You what now?

Let x be the minimum floor which an egg breaks when dropped from. Let the finite sequence (a_n), with a_n<x for all n except possibly the final n, describe an ordered list of drops made with one egg left, i.e. so that the nth drop is made from floor a_n, and a_0=j is taken to be the highest known safe floor (0 if there is no known safe floor.) Because there is one egg remaining, without loss of generality the first egg broke on floor k. Then j < x <= k Assume further that (a_n) is of minimum length and valid (in the sense that a_i=x or that a_i+1=x for some i. Observe that a sequence where a_(i+1)>a_i+1 for any i is not necessarily valid. Observe further that a sequence with a_(i+1)<a_i+1 is not of minimum length. Hence a_(i+1)=a_i+1 and (a_n) is precisely the sequence j+1, j+2, ..., x-1, x which has length x-j. This is bounded above by k-j-1 for all choices of x.

Now let (b_n) be strictly increasing and respresent some ordered list of drops made with two eggs remaining, as above. If an egg breaks on floor b_n, then b_n=k and b_(n-1)=j, so that the term k-j above is simply b_n - b_(n-1). If no eggs break, b_n=j and we may take k=100, so that k-j-1 becomes 99-b_n. We want to choose (b_n) such that the sum of the lengths of (a_n) and (b_n) is minimal. But by our work above, (a_n) is uniquely determined by (b_n) for a fixed x and has length at most max(k-j-1, 99-j).

The sequence (b_n) ending with b_i=k has length i and so we want to minimize max (i+k-j-1, i+99-j.) Precisely, to account for arbitrary x, we want to minimize f((b_n)) = max[b_1, 1+(b_2-b1), 2+(b_3-b_2), ..., i-1+(b_i-b_(i-1), ..., n-1+(b_n-b_(n-1)), n+99-b_n].

>>9884952 (cont)
The algorithm given in this thread has already been demonstrated to give sequences with |(a_n)|+|(b_n)| at most 14. It remains only to be shown that f((b_n))>13 necessarily. Contrariwise assume the b_1, 1+b_2-b_1, ... are each at most 13. Note b_i-b_(i-1) decreases by (at least) 1 every time i increments by 1 to preserve this property. But this contradicts our choice of strictly increasing (b_n), establishing the result.

>>9884951
It's true that in the worst case scenario you'd have to try 50 floors. Your point being?

>>9884950
>until the first egg breaks
>it's the best you can do
you have two eggs numbnuts

>>9884960
Yeah I know. Reread my solution, brainlet

>>9884961
reread the problem statement, brainlet

>>9884962
It must be hard going through life with a sub 80 IQ

>>9884964
this is you rn
https://www.youtube.com/watch?v=_YL4nCdCiLc

>>9884955
there are algorithms that give you a better worst case scenario.

>>9884964
are you in CS?

>>9884968
Kys
>>9884970
Such as?

>>9884970
Also I'd dispute that it's even possible for the worst case scenario to be less than 50 tries regardless of the algorithm, since you get one "try" and that 50 is half of the total.

>>9884972
Yes.

>>9884974
read the thread

>>9884974
throw the first egg from floor 10, 20, 30, 40, 50, 90 until it breaks
then try 1-9 or 11-19 etc with the second egg
max 18 drops

>>9884979
this has to be someone falseflagging as a CS brainlet

>>9884952
>>9884954
jibberish

>>9884952
If B(x) is the number of 2 egg drops to find x and A(x) is the number of one egg drops to find x then we want to minimize the sum of all these not individual terms.
>Precisely, to account for arbitrary x, we want to minimize f((b_n)) = max[b_1, 1+(b_2-b1), 2+(b_3-b_2), ..., i-1+(b_i-b_(i-1), ..., n-1+(b_n-b_(n-1)), n+99-b_n]
It's not immediately obvious why this is true, but the argument is better structured than before.
Now, there are two different things we need to choose, a two egg drop plan, b, and a one egg drop plan, a. The latter must be safe while the former can be more cavalier. This means that any a must be a bottom up check every floor.
I'm gonne try a uniform b with intervallength n so x=(B(x)-1)*n+A(x) unless x=m*n then add one, example, x=34 and n=7 then B(x)=5 and A(x)=6 and 34=7*4+6 but if x=35 then 35=7*4+6+1. So x=B(x)+A(x)-n(+1 if no remainder) and this is almost what we wanted to minimize. D(n)=sum(B(x)+A(x))=sum(x+n(-1 if no remainder))=5050+100n-100/n.
If I try to minimize this it goes to shit, not sure what went wrong.

>>9885126
Ahh shit, forgot that it's B(x)n not B(x) so
x=nB(x)+A(x)-n(+1)=B(x)+A(x)+(n-1)B(x)-n(+1)
and
D(n)=5050+(n-1)sum(B(x))+100n-100/n
B(x) is simply 1 for the first n numbers, 2 for the next n etc. so the sum(B(x))=n+2n+3n+... with 100/n terms so ~n*100/n*(100/n+1)/2=50*(100+n)/n=5000/n+50
and
D(n)=5050+(1-n)*50*(100+n)/n+100n-100/n
=5050+5000/n+50-5000-50n+100n-100/n=100+50n+4900/n
so
0=50-4900/n^2
n^2=4900/50
n=sqrt(98)~9,9
D(10)=1090 which means that the average drop is 10,9 which is over the 14 decremental tactic. So any uniform tactic is worse.

You fucking retards the egg is going to break on the first floor.

Holy fuck go outside.

t. phd math 300k starting @ google

>>9885126
>It's not immediately obvious why this is true
Yes, it is. Our choices of where to drop egg one serves to partition the floors into various intervals. Whichever interval x falls into will have an egg break at its upper end. Say it takes n drops to get to the first egg breaking and m more drops to check the remaining floors in the interval from the bottom to the top. Then if x was in that interval, the worst case will take n+m drops.
Why do you use a max? Because you don't know where x is. The -worst- interval for x to fall into, with respect to total number of required drops to find it, is the interval with the maximum n+m corresponding to it.
Each i-1+(b_i-b_(i-1)) is literally just (number of first egg drops) + (remaining floors in the interval to check, i.e. excluding the one top floor which -either- is one you broke an egg on -or- is floor 100, which you know is x if 99 comes back clean)

>I'm gonne try a uniform b with intervallength n so x=(B(x)-1)*n+A(x) unless x=m*n then add one, example, x=34 and n=7 then B(x)=5 and A(x)=6 and 34=7*4+6 but if x=35 then 35=7*4+6+1. So x=B(x)+A(x)-n(+1 if no remainder) and this is almost what we wanted to minimize. D(n)=sum(B(x)+A(x))=sum(x+n(-1 if no remainder))=5050+100n-100/n.
>If I try to minimize this it goes to shit, not sure what went wrong.
What are you talking about? I literally just solved it, with a formal proof. Not sure what you're trying to do.
>the number of 2 egg drops to find x
>minimize the sum of all these not individual terms
Huh?

>>9884926
https://brilliant.org/wiki/egg-dropping/#a-better-approach

>>9885232
You are trying to minimize the individual intervals, but you haven't proven that you can't have a winning strategy that has great variation in intervals. So that the overall steps are decreased while some of the intervals are large. Therefore you haven't proven your claim while I have proven, sorta, that the 14 decremental tactic is better than any uniform tactic.

>>9885236
>https://brilliant.org/wiki/egg-dropping/#a-better-approach
This isn't complete either, all they say is that you don't exceed 14 drops for each floor but it doesn't say why it's the best tactic. Why couldn't a tactic with 20 drops on one interval and 5 on all the others be better, this is almost certainly impossible but it hasn't been argued against.

>>9885245

>>9885239
>you haven't proven that you can't have a winning strategy that has great variation in intervals
Why do you think I need to do that? At-most-14 is possible, at-most-13 is provably impossible. Since we're optimizing for number of drops, any algorithm that gets it in 14 drops is "optimal." Simple.
>So that the overall steps are decreased while some of the intervals are large
I showed the nth interval can't be larger than 15-n (or the 14 solution will outperform it)

>>9885245
>Why couldn't a tactic with 20 drops on one interval and 5 on all the others be better
Because you need 19 egg drops to examine that interval, you absolute incorrigible fucking brainlet

>>9884619
>show everyone else that it conveniently works without actually proving it
>show it works
>without proving it
Boy howdy, you're gonna have a tough time with the second page of baby rudin

>>9885249
If I take 19 drops on one interval but I'm way more efficient on other intervals might still win a 14 drop on every interval unless you can prove otherwise. Stop using ad-hominem and prove your statement rigorously.

I see how much force is required to break one egg and then calculate which floor would give it enough acceleration to impart that force on contact with the ground.

>>9885256
In case you need it, the problem is asking for a tactic that minimizes [math]D=\sum_{x=1}^100A(x)+B(x)[/math]
where A(x) and B(x) are two egg drops and one egg drops to find floor x(if you lack the creativity to infer the meaning there, it's where you drop an egg with 2 still remaining and 1 remaining respectively). D is the total number of drops across every floor, you're trying to be effective, not minimize the max number of drops, unless they coincide, which you would also have to prove.

>>9885262
Oh, and you have shown that A(x)+B(x)<=14 so D<=1400, but even the uniform 5 interval tactic is better than that so that doesn't help much.

>>9885256
>Stop using ad-hominem and prove your statement rigorously.
Sure
19>14
QED
Further reading: >>9884952 >>9884954

>>9885262
Nope. The problem is to minimize the max number of drops, see:
>>9882362
>>9882858
>>9884681
>>9884951
>>9884970

Binary search?

>>9885287
see
>>9882253
>How should you find this floor with the smallest number of egg drops
It would be insane to interpret this as minimizing the worst case, if I find a tactic that by some magic does every floor in one drop but one in 15 you would still say yours is better? This is lunacy. The only reasonable interpretation is minimizing drops across all floors as stated above.

>>9885267
>D<=1400
nobody gives a fuck about your D
I think I see what's going on here, though. You deliberately reinterpreted it as "minimize the sum over all floors of the number of drops which would be required to find that floor is x," without telling us, because you're trying to be a wiseass or something. Which is ridiculous because the problem said nothing whatsoever about a distribution, much less a uniform one. The key floor is arbitrary but pre-fixed, and if it was a distribution, physical intuition says it would be heavily, heavily skewed.

If you want to go after a different problem than everyone else that's fine, but you have to say you're attempting something different instead of shitting down people's throats about why they're wrong, in replies to their solutions to the actual problem

>>9884849
It gets spammed all over the thread, the one with smaller and smaller steps, stop being retarded

>>9885307
I know you probably didn't read
>>9885303
but no sane person would choose the 14 tactic over that considering the problem as stated.

>>9882253
>>9882264
>>9882271
>>9882275
>>9882284
>>9882287
>>9882289
>>9882290
>>9882291
>>9882311
>>9882352
>>9882350
>>9882982
>>9883024
>>9883204
>>9883484
PIC RELATED IS THE ABSOLUTE STATE OF /SCI/

>Start from n=1st floor
>if it doesn't break drop it from n+1 floor
>if it breaks congrats you have your floor
>egg used : 1

>>9885314
In fact, if you worked in a team of two and you disagreed on which was better so you went to the boss and asked him to settle the dispute the 14 tactic dude would be fired on the spot.

>>9885322
and egg drops: (n)
You're the fucking retard who doesn't understand the point of the problem

>>9885303
>find it in 19 drops
>this is better than finding it in 14 drops

>>9885339
If all the other drops are 1 drops, then yeah, it's way better.

>>9885343
nope, you don't know where the floor is, you want to be able to find it within the least number of drops, regardless of the probability

>>9885348
That's an assumption of your own and not included in the problem as stated. I treat all the floors equally.

>>9885303
>if I find a tactic that by some magic does every floor in one drop but one in 15 you would still say yours is better? This is lunacy.
If the pre-fixed floor is that 15, yes. If the pre-fixed floor is not that 15, then no. Unfortunately before we start the algorithm there's no reasonable basis at all for speculation as to which of these cases is "likely" to occur. What you're describing isn't "better 99% of the time" because we don't have any reason to believe that those 99 floors are each equally as likely as the other 1 to be the key floor.
The only sane metric for comparing these algorithms is the objective one we do have, i.e. their upper bounds. As counter-intuitive as that may seem to brainlets like you.
>The only reasonable interpretation is minimizing drops across all floors as stated above.
My god, you can't even do your warped version right! Why are you weighting a 13 and a 15 as two 14s for christ's sake. Why wouldn't you at least minimize the sum of the squares instead? Why not cubes? How do you decide?
Maybe you realize that's not what was asked.

>>9885314
>no sane person
HURRR
You can take that like mind fallacy up with the whole rest of the thread, buddy

>>9885324
>muh boss
So you're removed enough from "real world" reasoning that you think a uniform distribution is a reasonable assumption to make for this problem, but now you're playing the MUH BOSS card?
The boss would explain exactly what he wanted optimized you fucking retard. He would say explicitly whether he wants the lowest expectation or the lowest worst-case, not force you to guess what he wants and mistake your guessing wrong for technical incompetence. Maybe he can only afford 14 drops, who the fuck knows.
But there's obviously no boss or practical importance here because a physical egg would break from a fucking three foot drop

>>9885351
>That's an assumption of your own and not included in the problem as stated

>>9885351
that's wrong and (You) are a retarded piece of shit, but the best "average" solution is still the one we are talking about, or one of the minor variations afforded by the fact that 100 is less than the 14th triangle number

>>9885355
You are out of your fucking mind if you think anyone would pick 14 over 15 and ones, regardless of the distribution.
The boss gave you the problem as stated, and fires anyone who says 14 over 15 and ones, guaranteed.
The reason I bring the "real world" into this is because both approaches require assumptions, I'm just trying to show that your assumptions are batshit insane.

>>9885360
I never said it wasn't the optimal solution, I just said it hadn't been proven yet.

>>9885417
The absolute state of /sci/.

>>9885417
it wouldn't be 15 and ones regardless, you fucking imbecile, it would be more like trying the 10 most common ones in hopes of finding them in 1-10 drops and then doing a less retarded strategy for the remaining floors, with a much worse result both in worst case and on average (if even distribution)

>>9885430
I agreed when I proposed the 15 and ones strategy that it was ludicrous, but the point was that the optimality of the 14 strategy hadn't been proven, I think it's quite likely it's optimal to be honest. But you are trying to prove it by insult, which isn't very effective unless you are much more qualified than your reader, which you aren't.

>>9885322
This has got to be bait

>>9885444
it's optimal in terms of the upper bound, which is what we (perhaps not (You)) are interested in

3. 0

>>9885460
You still don’t grasp his point. What if there are multiple methods with the same maximum as 14, but on average, one solution has a lower number of egg drops?

>>9885642
he's talking about other maximums as well
you can count the ones with max 14 on one hand, all based on the same method, minor variations because 100 is below the 14th triangle number, i don't care to find out their averages though, why don't you do it

>>9882311
>>9882316
how can you find 14 from this?

>>9885656
>>9884831

>>9882982
>Matlab brainlet.

Have fun paying $2000 a year for a license once you graduate in order to retain a relevant skillset.

>>9884831
impressive

>>9885690
>paying for matlab

>>9885690
lel, I remember a prof handed out to us a perfectly working pirated Matlab 2016 version

you must be a retard if you pay these kind of expensive shit

Here you all go:
https://www.youtube.com/watch?v=NGtt7GJ1uiM

>>9882253
Start from the 2nd floor, keep adding 2 floors until it breaks, then go down 1 floor, anfmd if the egg breaks, it's the floor below that, if it doesn't, it's that floor

>>9885970
>51 drops to find out it breaks on floor 100
Very efficient

>>9885970
This is my D(2)=100+50*2+4900/2=2650 for an average 26,5 drops per floor to find the egg which is extremely inefficient, since we've found methods that go below 10 drops per egg.

>>9885879
For the problem stated as here the 14 decremental tactic has probably been proven optimal in this thread. But this problem is not stated as in OP which is critical.

You're all really dense.
>drop eggs at intervals of 10 floors
>when it breaks, start with intervals of 1 at the end of the last interval
For example:
>drop egg on floor 10
>doesn't break
>floor 20
>doesn't break
>floor 30
>breaks
>take second egg drop on floor 21
>doesn't break
>floor 22
>doesn't break
>floor 23
>breaks
You'd need at most 20 drops.

>>9886250
You're really late to the party, there is a tactic that has 14 drops max for all floors which also has an average drop of about 9 eggs for each floor. The uniform 10 tactic you mentioned is the optimal uniform tactic but it still requires about 10,9 drops per floor on average.

>>9886259
Oh shit, I typed up the post a while ago, but forgot to click "post", so I uploaded it just now. My bad.

Start at floor 1 and work your way up. You break one egg. How is this hard?

>>9886274
You try and minimize the number of throws, not eggs broken.

>>9885322
>>Start from n=1st floor
>>if it doesn't break drop it from n+1 floor
>>if it breaks congrats you have your floor
>>egg used : 1
This but n +3 instead of n+1.
And if eggBreaks == true, n-1
And if eggBreaks == true the highest floor the egg doesn't break on is one floor lower than the one you last dropped a egg on.
Assuming egg doesn't break at floor 1, it breaks when dropped from floor 4, than we drop our next egg from floor 3, it also breaks so the highest floor it can be dropped from without breaking would be floor 2

>>9886323
It could also be floor 1.

>>9886338
The first egg drop was at floor 1
People are optimizing for the odds of the egg breaking being equal for all the floors.
Realistically, no matter how hard boiled an egg is, dropping from the tenth story will break it.
Therefore starting at the first floor and then increasing by one is the most effective method because it's most likely to break on floor 1 and then becomes less likely to break on every subsequent floor.
(Because if it doesn't break on floor 99, who can say it'll break at all within the hundred floors, maybe it needs to be dropped from 130 floors to break it)

>>9886368
Yeah, and you still don't know it's not 1 unless you drop at 2.

>>9882253
These are very poorly phrased.

>>9882290
Alright so drop an egg on the 1st floor lol

>>9882253

1. Start from the bottom and work your way up. Keep droppin them eggs till they break.

>>9885970

This be the solution, I feel

W-what if you have 3 eggs?

>>9882320
Idea is to choose a shrinking interval such that the number of drops to find the interval of balanced by the size of the interval when you find it

>>9887173
What if you have 100 eggs?

>>9887222
Binary search

>>9887222
What if you have 10,000 eggs?

>>9887173
>>9884843

>>9882316
The solution given there is actually wrong.
There needs to be another 1st egg drop at floor 99, otherwise you'll go over 14 drops testing the last five floors.

Although the worst case in that solution is 14 (with floor 99 included), and that is optimal, by other criteria that solution is perhaps not the best.
The number of worst cases is 22 (i.e. when the last safe floor is directly below a first egg drop, or is the floor directly below that), and the average number of drops needed is 10.36.

If instead you dropped first on [13,26,38,49,59,68,76,83,89,94,98], the average drops to 10.35, and you drop to 21 actual worst cases. You get away with doing two 13 floor gaps, so the worst case 14 drops start after testing floor 26.


[12,24,36,47,57,66,74,81,87,92,96,99] lowers the average to 10.34, but still has 21 worst cases. This time three 12 floor gaps, so worst case 14 drops start after floor 36, but then you gain a worst case back at the top because there's an extra 1st egg drop.


I don't know if this is optimal, though, while staying within 14 drops as worst case.

>>9884589
> if you proved it broke on floor 2 why drop on floor 4?
I hate eggs. And Jews. But I can't very well drop a Jew from the 4th floor of a building, can I?