The error diminishes faster than my english marks

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?


The answer is 5380.

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.

2 solutions

Michael Mendrin
Jul 1, 2018

We can look at all the possible choices of positive a , b < 50 a, b<50 that can result in the 2nd largest number 3325 and see what is the next number. The 9 9 th to 14 14 th Fibonacci numbers are 34 , 55 , 89 , 144 , 233 , 377 34, 55, 89, 144, 233, 377

34 a + 55 b = 34 25 + 55 45 = 3325 34a+55b=34\cdot25+55\cdot45=3325
55 25 + 89 45 = 5580 55\cdot25+89\cdot45=5580

55 a + 89 b = 55 20 + 89 25 = 3325 55a+89b=55\cdot20+89\cdot25=3325
89 20 + 144 25 = 5580 89\cdot20+144\cdot25=5580

89 a + 144 b = 89 5 + 144 20 = 3325 89a+144b=89\cdot5+144\cdot20=3325
144 5 + 233 20 = 5580 144\cdot5+233\cdot20=5580

144 a + 233 b = 144 15 + 233 5 = 3325 144a+233b=144\cdot15+233\cdot5=3325
233 15 + 377 5 = 5580 233\cdot15+377\cdot5=5580

Thus, Houdini had all the bases covered. 5580 5580 is the only possible largest number, given the conditions.

Jerry Bao
Jun 25, 2018

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 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 a_{n}=a(\varphi )^n+b(1-\varphi )^n where phi represents the golden ratio.

Consider the ratio between a n a_{n} and a n 1 a_{n-1} as n grows large: a ( φ ) n + b ( 1 φ ) n a ( φ ) n 1 + b ( 1 φ ) n 1 \frac{a(\varphi )^n+b(1-\varphi )^n}{a(\varphi )^{n-1}+b(1-\varphi )^{n-1}}

Because 1 φ \left |1-\varphi \right | is less than 1, b ( 1 φ ) n b(1-\varphi )^n and b ( 1 φ ) n 1 b(1-\varphi )^{n-1} quickly converge to zero, so the ratio between a n a_{n} and a n 1 a_{n-1} converges to φ \varphi .

Houdini simply multiplied 3325 by φ \varphi 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.

Michael Mendrin - 2 years, 11 months ago

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?

zico quintina - 2 years, 11 months ago

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

Jerry Bao - 2 years, 11 months ago

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.

Michael Mendrin - 2 years, 11 months ago

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.

Jerry Bao - 2 years, 11 months ago

Log in to reply

@Jerry Bao You can rest easy now. I've put in my solution.

Michael Mendrin - 2 years, 11 months ago

5380 is the only possible next term under the conditions given.

Michael Mendrin - 2 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...