Author |
Topic: The Devil, Swans, 2 Eggs and a 100-story Building. (Read 5774 times) |
|
rloginunix
Uberpuzzler
Posts: 1029
|
 |
The Devil, Swans, 2 Eggs and a 100-story Building.
« on: Feb 21st, 2014, 7:57am » |
 Quote  Modify
|
The Devil, Swans, 2 Eggs and a 100-story Building.
What do the Devil, Swans and 2 eggs and a 100-story building all have in common?
(This is the third and the final problem in a series of three related ones. The first two are "The Devil and the Loiterer" and "Swan Lakes").
|
| « Last Edit: Mar 15th, 2014, 9:08am by rloginunix » |
 IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #1 on: Feb 21st, 2014, 1:27pm » |
Quote Modify
|
damn it, i really hoped it will be some complex riddle consisting of parts of these other riddles
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #2 on: Feb 22nd, 2014, 2:09am » |
Quote Modify
|
What, like dropping swan-eggs from a hundred story building onto the devil loitering below?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #3 on: Feb 22nd, 2014, 9:12am » |
Quote Modify
|
Each of these problems has multiple parameters
The Swans:
a) No. of Swans.
b) No. of Lakes.
c) No. of Swans that land on a lake.
d) No of Swans remaining in the end.
The Devil and the Loiterer:
a) Initial amount.
b) The factor by which the money multiplies.
c) The amount to be given to the devil.
d) The number of times the bridge is crossed.
e) The amount remaining in the end.
2 Eggs and 100 floor building
a) No. of Eggs.
b) No. of Drops.
c) No. of Floors.
d) No of eggs allowed to be broken.
And each of these problems can be framed as:
Given some of the parameters, find the others.
|
|
IP Logged |
All signatures are false.
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #4 on: Feb 22nd, 2014, 10:02am » |
Quote Modify
|
gotit, all of your statements are correct and true but your conclusion is too generic, it can be applied to any hard science problem.
You are moving in the right direction. The intended answer is more specific.
You guys are wickedly smart so I don't want to say something that will give the answer away.
There's a deeper connection between these problems. I've selected them for a reason. Take that depth one notch down.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #5 on: Feb 22nd, 2014, 1:45pm » |
Quote Modify
|
Think problem solving mechanics.
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #6 on: Feb 22nd, 2014, 7:46pm » |
Quote Modify
|
on Feb 22nd, 2014, 2:09am, towr wrote:| What, like dropping swan-eggs from a hundred story building onto the devil loitering below? |
|
was thinking rather sth like you drop egg from a story, then you cross one of the bridges and after multiplying devil takes away amount of money equal to how many floors you went up from previous try, and bridges are over lakes each time you cross it swans land on this lake, there is also a map that defines what bridges you might cross from where, and in the end when you finally find from what exact story egg breakes it turned out 1 last swan landed you need to use gold you have to feed swans from the lake where median number of swans is 
|
| « Last Edit: Feb 22nd, 2014, 7:47pm by riddler358 » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #7 on: Feb 23rd, 2014, 8:58am » |
Quote Modify
|
All three problems can be solved in a straightForward way which is rather laborious. But there is more than way to solve a problem.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #8 on: Feb 23rd, 2014, 11:17am » |
Quote Modify
|
The devil and the swans can both be solved by brute force (think of a number, see what result it would give, repeat until you get the right result) or by reversing the process (start at the end result and apply the reverse of the repeated step).
Both problems are of the form: fn(k) = r, where f, n and r are given and k is to be found.
It's not obvious that they have a commonality with the egg-drop problem, which asks you to find the minimum worst-case number of drops over all possible dropping strategies - so brute force would require first coming up with a list of viable strategies, and then testing all of them, and there isn't an end result given to work backward from - you can show that the answer must be at most X fairly easily, but any form of lower bound requires actual insight rather than mere calculation...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #9 on: Feb 23rd, 2014, 11:50am » |
Quote Modify
|
rmsgrey, all in all you are correct. Reverse Order problem solving approach is what I was after and what I think unites all three problems. No pun intended, but in normal order from easy to hard here's what I mean.
"The Devil and the Loiterer".
It is of course easy enough to solve this problem with a forward logic. Let x be the original amount of money. Immediately after the first bridge crossing it becomes 3x. Right before the second crossing it's 3x - 27. Right after the second crossing it's 3*(3x - 27). Right before the third crossing it's 3*(3x - 27) - 27. Right after the third crossing it's 3*(3*(3x - 27) - 27). And after the devil takes his fill the equation is 3*(3*(3x - 27) - 27) - 27 = 0.
Solving it using the Reverse Order approach we start with the third bridge crossing and proceed backwards towards the "before the first crossing" state. We also reverse the meaning of the arithmetic operators. Subtraction becomes addition, multiplication - division. Since after the third bridge crossing no money was left in the loiterer's pockets and the devil's take is $27 then that's exactly how much money the loiterer has. Right before the third crossing it's 27/3 = 9. Right after the second crossing it must be 9 + 27 = 36. Right before the second crossing it's 36/3 = 12. Right after the first crossing it's 12 + 27 = 39. Right before the first crossing it must be 39/3 = 13.
The benefit of the Reverse Order is not very convincing at this point because the number of repetetive steps is low. That's why there are "Swan Lakes".
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #10 on: Feb 23rd, 2014, 12:03pm » |
Quote Modify
|
"Swan Lakes".
Solving it with forward logic let x be the number of swans that approached the first lake. The number of swans that landed there is x/2 + 1/2. The number of swans that carried on to the second lake is x - (x/2 + 1/2). The number of swans that landed on the second lake is (x - (x/2 + 1/2))/2 + 1/2. The number of swans that carried on to the third lake is x - ((x - (x/2 + 1/2))/2 + 1/2). And so on. Doable? Yes. But cumbersome and error prone. What if we had 1000 lakes?
Reverse Order approach.
Start with the 7-th lake and work your way backwards. We can reword the problem statement slightly by finishing it thus: "... and zero swans carried on to the 8-th lake". It means that all the swans (x) that approached the 7-th lake landed there:
x = x/2 + 1/2
2x = x + 1
x = 1
After that we add (reverse of subtract) 1/2 to x and then we multiply (reverse of divide) the result by 2. We call it x again and repeat this process 6 times: 3, 7, 15, 31, 63, 127.
Alternative (and more verbose) reverse order solution that also works:
One swan landed on the 7-th lake and, by the same token, that's how many swans were left after some amount of them landed on the 6-th lake. So if x is the number of swans that approached the 6-th lake then:
x - (x/2 + 1/2) = 1
2x - x - 1 = 2
x = 3.
Three swans approached the 6-th lake. Working our way in reverse let x be the number of swans that approached the 5-th lake:
x - (x/2 + 1/2) = 3
x = 7
Seven swans approached the 5-th lake. For the 4-th lake we get:
x - (x/2 + 1/2) = 7
x = 15
And so on. 31 swans approached the 3-rd lake. 63 swans approached the 2-nd lake. 127 swans approached the 1-st lake.
But you don't have to solve the entire problem this way. It may be subjective but I think it's fairly easy to spot the pattern when going in reverse. The number of swans that approaches the k-th lake is 2^(7-k+1) - 1 and the number of swans that lands on the k-th lake is 2^(7-k). The overall process is less error prone and we can figure out the formula relatively quickly.
[edit]
Added a more mechanic reverse order solution.
[/edit]
|
| « Last Edit: Mar 12th, 2014, 9:19pm by rloginunix » |
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #11 on: Feb 23rd, 2014, 12:45pm » |
Quote Modify
|
on Feb 23rd, 2014, 11:17am, rmsgrey wrote:| It's not obvious that they have a commonality with the egg-drop problem, which asks you to find the minimum worst-case number of drops over all possible dropping strategies - so brute force would require first coming up with a list of viable strategies, and then testing all of them, and there isn't an end result given to work backward from - you can show that the answer must be at most X fairly easily, but any form of lower bound requires actual insight rather than mere calculation... |
|
for the standard egg dropping problem isn't it enough to find lowest integer for which k(k+1)/2 >= 100
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #12 on: Feb 23rd, 2014, 3:30pm » |
Quote Modify
|
"2 Eggs and a 100-story Building".
For a full disclosure I have to say that that's obviously not how I was solving this problem originally. Hind sight is always prefect. No prior knowledge condition doesn't hold. As such the following Reverse Order solution was affected by the knowledge of the right answer.
Let's assume that according to some scheme we've got to the 100-th floor. Let's work in reverse order by answering the following question: from which lower floor did we get to this higher floor?
On the 100-th floor we execute the last N-th drop. From which floor did we get here? Think of yourself climbing, say, 10 steps. In reverse order which step were you on before stepping onto the 10-th one? Or find the analogy with all the remaining swans landing on the last lake.
Back to the eggs. It should be fairly logical to assume that all the testing work that had to be done has been done at this point. For the worst case scenario - the 100-th floor is bad (or not) - this is it. There should be no extra floors left to test between the N-th and (N-1)-st drops. In other words we got to the 100-th floor from the 99-th floor. Moving in reverse order we descend 1 floor down from 100 to 99 so that the scheme so far is 100, 99.
If the first egg doesn't break on the 99-th floor in at most 1 test we solve the problem by executing the final drop from the 100-th floor. If it does then we use the second egg. With the same 1 drop we can test 1 floor - the 98-th one. Keeping the "test all floors optimally" requirement in mind, from which floor did we come to the 99-th one? Since the 98-th floor is tested it should be the 97-th. So we descend to the 97-th floor and the scheme is 100, 99, 97.
If the first egg doesn't break on the 97-th floor in at most 2 tests we cover all the floors above: {99, 100} or {99, 98}. If it does then with the second egg with the same 2 drops we can test floors 95 and 96. From which floor, then, did we come to the 97-th floor if floors 95 and 96 are covered? From the 94-th one: 100, 99, 97, 94.
If the first egg doesn't break on the 94-th floor in at most 3 tests we cover all the floors above: {97, 95, 96} or {97, 99, 98} or {97, 99, 100}. If it does then with the same 3 drops we can test the floors 91, 92 and 93 and it should be clear that we've got to the 94-th floor from the 90-th: 100, 99, 97, 94, 90.
And so on. Moving in reverse order we descend by 1 floor for the tests done by the first egg, but since the second egg intervenes we descend by an ever increasing number of floors down until we run into negative numbers and the scheme looks like:
100, 99, 97, 94, 90, 85, 79, 72, 64, 55, 45, 34, 22, 9, -5
As Grimbal noted earlier there seem to be 2 schemes for each building. So I think it is also fairly logical to assume that after some pondering a problem solver will hit upon the idea of shifting the entire testing ladder up by 5, in this case, floors or by simply adding 5 to each entry in the scheme. After all it's just renumbering the floors so as to not waste the 5 floors in the basement:
105, 104, 102, 99, 95, 90, 84, 77, 69, 60, 50, 39, 27, 14, 0
And all the other good things we've talked about earlier can be discovered as a result.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #13 on: Feb 24th, 2014, 5:40am » |
Quote Modify
|
on Feb 23rd, 2014, 12:45pm, riddler358 wrote:
for the standard egg dropping problem isn't it enough to find lowest integer for which k(k+1)/2 >= 100 |
|
Yes, but you need to prove that first.
You can also show that there are only 2^99 possible strategies for dropping the eggs - okay, there are infinitely many strategies of the form "drop from floor n; if the egg doesn't break, drop it from floor k<n some number of times before moving to another floor" but if you add the constraints that you can only drop from floors where you don't already know what would happen, that your strategy has to be able to pin down any floor, and that your strategy has to be entirely deterministic, then you get the 2^99 possibilities:
Any "valid" strategy must drop the first egg from some floor, then from a higher floor, then from a higher floor, etc until it breaks or is dropped from floor 100. When the first egg breaks, you then have an interval to explore with the second egg - since you have to visit every floor in the interval (unless the egg breaks first) and you have to visit floors in increasing order, you have to start with the lowest floor in the interval and move up through them in order until the egg breaks.
Any valid strategy is therefore entirely determined by specifying which subset of the first 99 floors you drop the first egg from - 2^99 possibilities. Too many to brute force...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #14 on: Feb 24th, 2014, 8:19am » |
Quote Modify
|
I own a clarification of my terminology. I call them approaches because they are not methods and even more so not laws. Laws are way too universal, all encompassing and formulaic. Methods are (almost) machine-ready algorithms that require little or no modifications from case to case.
Approaches are not machine-ready, not as formal and they have quite a bit of wiggle room.
This was my standard exercise in solving a problem any which way I can (2 eggs) and then searching for as simple a solution as I can muster.
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #15 on: Feb 24th, 2014, 10:46am » |
Quote Modify
|
i didn't see that at first, it's nice, i would even say that from computational point of view it's very nice, but in terms of explaining to someone i would go for normal way not the reverse, and then inspired by your solution i would say "switch to reverse" at the sum from k to 1 (instead using formula), just making it sum from 1 to k then and stop when exceed 100
also i didn't get why for swans you do calculations with 'x', you said yourself just reverse the order of operations switching to opposite, hence start from 1 and just add half swan and then multiply by 2, each time you do both you are on next lake
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #16 on: Feb 24th, 2014, 12:02pm » |
Quote Modify
|
on Feb 24th, 2014, 10:46am, riddler358 wrote:| i didn't see that at first |
|
Neither did I. See my full disclosure. Also if you follow the egg dropping thread you will see that all of us, me including, rushed into the solution the usual way, calculus was employed. Early in my deduction I mentioned that "... there's no symmetry here ... we can't climb to the 100-th floor right away and drop eggs from there ...". Ironic as its I didn't realize at a time that even though the actual tests can't be done that way a search for a solution can. It took me a lot of what ifs to get here. So reverse order can be used to obtain an analytic (non computer-based) solution which then can be, and should be, generalized.
on Feb 24th, 2014, 10:46am, riddler358 wrote:| also i didn't get why for swans |
|
Yes, you are right. I could've followed my own recipe but x is so much shorter than "the number of swans that approached the lake blah". Also, as captain Barbossa in "Pirates of the Carribbean" said "these are just suggestions". We all here like formulaic precision but getting too formal may hurt - reversing the order of arithmetic operations worked in some problems and may not make sense in others. Which arithmetic operation do we reverse in the eggs problem?
May be I'm missing something but the idea is to reverse the overall logic of a given problem and then adjust the meaning of it for each particular one.
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #17 on: Feb 24th, 2014, 2:56pm » |
Quote Modify
|
like u said in devil and loiterer, start from end and reverse operations, start from 0, add 27 then divide by 3, repeat 3 times
same for swans start from 1, add half, multiply by 2, repeat 6 times
and for egg dropping we are reversing sum from k to 1, solution goes like follows - you pick a story to drop first egg, let's say this story is k, then if egg breaks your worst case is k, and if it doesn't break you pick next story in a way that will not change your current worst case - k. Since you already used 1 drop, you can go up k-1 stories for next try, then when it breaks your worst case is still k, you go 1 less story with 1st egg each time it doesnt break, when you reach 1 you cant get any higher without exceeding k, so for starting story k you can test as much as k + k-1 + ... + 1, here i rushed to summation formula getting k(k+1)/2 >= 100 but instead we reverse and have 1 + 2 + .... and moment we reach or exceed 100 gives us answer
|
| « Last Edit: Feb 24th, 2014, 2:58pm by riddler358 » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #18 on: Mar 12th, 2014, 9:30pm » |
Quote Modify
|
To summarize the discussion of the three related problems I've updated the swans to follow the reverse order recipe more closely but there's a much bigger issue at stake here.
The truth be told I've originally set out to find a geometric interpretation of the 2 eggs problem. I recalled that in my previous ruler and compass solutions I've used the reverse order approach. That's how I've solved the equilateral triangle on three parallels problem, amongst others.
I've assumed that the required construction has somehow been done (by constructing an arbitrary equilateral triangle first and then adding the parallels). Next I asked myself "what useful observations can I make"? I decided to collapse the three parallels into two and derived an 11-step solution from there. Later on I cut it down to 8 steps. That 8-step solution was my standard "make it as simple as possible" exercise achieved via the 11-step solution achieved via the reverse order approach.
Sir Col obtained his solution, as he put it, "by working backwards", by using a rearrangement of a circular kind - rotation.
All this time I wasn't realizing that reverse order has its place outside of geometry. I flew past it fast and furious. Looking for a geometric interpretation of the 2 eggs problem, however, I said "what if"? That's why the silly Devil and Swans came in - as a testing ground. Then I was ready to apply the "new" approach to the problem ranked hard.
Now based on the mighty sample of three (disciplines) I'm ready to claim that the (newly identified) reverse order approach works across all of hard sciences and is now a part of my updated collection of Division, Elimination, Equation, Rearrangement, Reverse Order, Scope Expansion/Reduction, Space Time and Substitution.
Reverse Order:
Assume that a problem has been solved somehow. Start from this solved state and by working backwards attempt to reverse the logic of the problem to find a solution. The nature of the problem dictates the exact reversal steps.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #19 on: Mar 12th, 2014, 9:39pm » |
Quote Modify
|
We've seen the reverse order in action in algebra and geometry. In computer programming Reverse Order is cleverly disguised as a topic that not so long ago Baruch was looking for help with - recursion:
extern size_t
Factorial( size_t n )
{
if ( n == 0 || n == 1 )
{
return 1;
}
return n * Factorial( n - 1 );
}
extern size_t
Fibonacci( size_t n )
{
if ( n < 2 )
{
return 1;
}
return Fibonacci( n - 1 ) + Fibonacci( n - 2 );
}
These solutions start from "the end" by assuming that the problem has been solved somehow. By winding the stack they work towards "the beginning" - earlier and earlier terms - until the seed values are reached. At which point the recursion stops. By unwinding the stack they use the cached in (intermediate) values to calculate the result.
The life span of a single person is unfortunately not long enough to have an in-depth knowledge of all the hard science disciplines but more samples from various branches are fun to obtain and document.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: The Devil, Swans, 2 Eggs and a 100-story Build
« Reply #20 on: Mar 12th, 2014, 9:50pm » |
Quote Modify
|
In conclusion.
The hard part is, after reading a problem, knowing right away which approach will solve it. Grimbal has found a programmatic solution for the average 2 eggs case. That makes me think that there must be a programmatic solution for the worst case also. These programmatic solutions are an awesome tool. However, if we keep blindly adding eggs and floors to the building and keep only observing the printf()s on stdout all we will see is testing schemes, we will not gain the analytic insight into "why". Please don't get me wrong - in no way, shape or form am I criticizing the programmatic solutions. On the contrary. In some situations, I wager, a programmatic solution may be the only reasonable way to find an answer reasonably quickly.
The point I'm trying to make is that, using the 2 eggs problem as an example, programmatic or Reverse Order obtained testing schemes are just a tool to crack the analytic solution wide open. If I knew back then that I could've used the reverse order approach I think that that's all I would've come up with at first - a testing scheme. My next question would've been "why"? Not sure I would've jumped to k(k +1)/2 formula right away. Eventually, yes. But not instantly. But it's only me.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print