Houdini is trying to pick up chicks at the bar, but he is getting no luck. He then stumbles across a particularly voluptuous woman. In desperation, he tries to impress her with a magic trick.
Houdini: "Pick two distinct integers between 1 and 50 inclusive. Write them down on a piece of paper but don't show them to me."
Khalifa: "Okay."
Houdini: "Now add those two numbers together. Write the resultant number down on your paper. Again, don't show me your list!"
Khalifa (who was about to show Houdini her list): "Oh, okay."
Houdini: "Take the two largest numbers on your list and add them together. Write the resultant number down on your paper. Repeat this process as many times as you like."
Khalifa (after around a minute or so): "Okay, now what?"
Houdini: "Tell me the second largest number on your list."
Khalifa (pauses, scanning her giant list): "3325."
Houdini: "I bet I can guess what your largest number is."
Khalifa: "No way."
Houdini: (tips fedora, pushes up glasses, smirks) "M'lady, do you believe in magic?"
What number did he tell Khalifa?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let us list out the terms in Khalifa's list in increasing order: a1, a2, a3, a4, etc.
The terms of the sequence are defined by this relation: a n = a n − 1 + a n − 2
Finding the characteristic polynomial, we find that the general term is of the form: a n = a ( φ ) n + b ( 1 − φ ) n where phi represents the golden ratio.
Consider the ratio between a n and a n − 1 as n grows large: a ( φ ) n − 1 + b ( 1 − φ ) n − 1 a ( φ ) n + b ( 1 − φ ) n
Because ∣ 1 − φ ∣ is less than 1, b ( 1 − φ ) n and b ( 1 − φ ) n − 1 quickly converge to zero, so the ratio between a n and a n − 1 converges to φ .
Houdini simply multiplied 3325 by φ and rounded to the nearest integer (5380). Houdini is an A+ chad.
Man, one of the best bar tricks ever. I'd give it TWO likes if I only could.
I got the solution the same way, but how did you determine the necessary condition for the initial two numbers (having to be between 1 and 50)? Clearly if that condition were removed there would be other solutions. And is there a way to prove that 5380 is the only possible next term under this condition?
Log in to reply
I picked the range 1-50 to provide reference comparison to the number 3325. It should be clear to the reader that Khalifa repeated the process many times, allowing the ratio to converge very close to the golden ratio.
Now the sketchy part: although Houdini's process works 99℅ of the time, there are certain cases where the result can be off by 1. This is not one of those cases. If it were, Brilliant allows you to submit your answer three times, covering all three cases :P
Log in to reply
Once Khalifa has added about a half dozen times or so, then multiplying by the golden ratio and rounding off works reliably 100% of the time. Houdini just needed to convince her to keep adding for some time instead of letting her stand after a few additions.
In this case, if Khalifa picked two numbers < 50 and her 2nd highest number is 3325, then the largest number is unambigously 5380, regardless of what numbers she picked to get the 3325.
Log in to reply
@Michael Mendrin – You're probably right. In the cases where I was off by 1, I started off with pretty huge numbers. I just think it's sketchy because rigorously proving that it's unambiguously 3325 (showing the error diminishes enough to ensure precision within a specified number of tries) is a giant pain in the ass. I might be wrong though, but I can't think of any short proof.
Log in to reply
@Jerry Bao – You can rest easy now. I've put in my solution.
5380 is the only possible next term under the conditions given.
Problem Loading...
Note Loading...
Set Loading...
We can look at all the possible choices of positive a , b < 5 0 that can result in the 2nd largest number 3325 and see what is the next number. The 9 th to 1 4 th Fibonacci numbers are 3 4 , 5 5 , 8 9 , 1 4 4 , 2 3 3 , 3 7 7
3 4 a + 5 5 b = 3 4 ⋅ 2 5 + 5 5 ⋅ 4 5 = 3 3 2 5
5 5 ⋅ 2 5 + 8 9 ⋅ 4 5 = 5 5 8 0
5 5 a + 8 9 b = 5 5 ⋅ 2 0 + 8 9 ⋅ 2 5 = 3 3 2 5
8 9 ⋅ 2 0 + 1 4 4 ⋅ 2 5 = 5 5 8 0
8 9 a + 1 4 4 b = 8 9 ⋅ 5 + 1 4 4 ⋅ 2 0 = 3 3 2 5
1 4 4 ⋅ 5 + 2 3 3 ⋅ 2 0 = 5 5 8 0
1 4 4 a + 2 3 3 b = 1 4 4 ⋅ 1 5 + 2 3 3 ⋅ 5 = 3 3 2 5
2 3 3 ⋅ 1 5 + 3 7 7 ⋅ 5 = 5 5 8 0
Thus, Houdini had all the bases covered. 5 5 8 0 is the only possible largest number, given the conditions.