If you are in a hurry, you can skip the story below, there's a TL;DR near the end.
The gist is that we are going to solve every number-sequence puzzle ever*, all in one go.
*: Terms and conditions may apply. May be subject to availability. Contact your local maths department for further information.
Charlie, a university tutor, was having a get-together with his lot of freshmen, fortuitously nicknamed Wonder, Tootsie, and Trillian.
Unfortunately, they had 4N+1 cupcakes, so the question arose, who gets the last one.
Charlie: I don't think there's any other choice, we have to settle this the old-fashioned way.
Wonder: What, a duel? Isn't that a bit extreme?
Charlie: What? No, not a duel! A bet of course!
all around: (sighs of relief)
Charlie: I'm really good at number sequence puzzles, so here's the deal: You guys pick any fourth order polynomial, and calculate its value at any 5 points. As long as the distance between two consecutive points is always the same, I can tell you the next two numbers in the sequence. If I get them right, I get the cupcake.
Tootsie: Well, big whoopty-doo, we all know how to fit polynomials.
Charlie: Okay, but what if I do it only using addition and subtraction? No more than ten of either, too. Would that be impressive enough?
Trillian: Hey, I know this trick! You are going to combine the numbers into this one huge long string of numbers, and then claim that you are only doing one addition while you are actually doing several at the same time, aren't you?
Charlie: (looking a little offended) No, that would be cheating! I won't cheat in any way. I promise!
all around: (exchanging glances, hesitant nods gradually turn into a consensus of acceptance)
Wonder: Very well. The bet is on.
Charlie: Ok, you guys figure out the number sequence, while I go return some of that excellent cider to mother nature.
While Charlie is away, the freshmen try to decide how to choose the factors for the polynomial. They'll of course also need a starting point, and the distance between the points. (Names shortened to numbers just because.)
1: Well, I'll just jot down a couple of numbers then, we'll use those as the coefficients of the polynomial, and..
2: NOT SO FAST! How do we know you are not colluding with Charlie? We all know you have a crush on him!
1: Well, so do you, so..
3: Shut up, you two. We'll use the digits of pi.
1: ..Yeah, that's probably fair. That would only give positive coefficients though.
2: So we'll subtract 5 from each digit.
3: That should work. There's a 5 in the first digits of pi though, getting a zero in one factor might make the sequence easier to solve.
1: Well, let's use "e" then.
2: Yes, let's.
So Trillian rolls up her sleeves, and starts writing. This is what she wrote:
[2, 7, 1, 8, 2, 8, 1] (minus 5) -> [-3, 2, -4, 3, -3, 3, -4]
-> $\mathbf{-3x^4 + 2x^3 - 4x^2 + 3x - 3}$, First point: 3, Step: -4.
"These numbers are going to get big. Anyone have a calculator? Thanks... I really don't think Charlie can solve this. I mean, even I have to do a silly number of multiplications here.."
Point: 3, -1, -5, -9, -13, -17, -21
Polynomial value: -219, -15, -2243, -21495, -90795, -261599, -603795
Trillian: Ok, those got pretty huge. Even it he could somehow figure them out, it's probably going to take a good while.
Charlie returns, and is handed this list of numbers: -219, -15, -2243, -21495, -90795. He then performs ten simple subtractions, followed by eight additions (the last four he calculates in one go), and grabs the cupcake less than two minutes after his return.
The freshmen stare at the correct result incredulously, until Wonder exclaims "That's bloody brilliant!" and goes to fetch Charlie another pint of cider.
What were Charlie's calculations?
TLDR:
Given a sequence of five ($N+1$) numbers, of which you know that they were generated by evaluating an unknown fourth ($Nth$) order polynomial at regular intervals, how can you extrapolate the next two values using 10 ($\frac{N^2+N}{2}$) subtractions and 8 ($2N$) additions only?
For extra credit, can you name another Charles whose name is in the history books in big part for implementing this same method very cleverly?
For another bonus point, why did Trillian roll up her sleeves?
For super-hyper-extra points, what would have happened if Trillian had made a mistake while calculating one of the five numbers?
No comments:
Post a Comment