Prove that every natural number can be written as a sum of unique (ie. non-repeated) fibonacci numbers.
Proof sketch: use a greedy algorithm.
Proof: for a given number N. Find the greatest fibonacci number less than or equal to N; call this Fn. Now, N < Fn+1 = Fn-1+Fn, so N-Fn < Fn-1. Therefore, the algorithm can be repeated while only ever using strictly smaller fibonacci numbers, maintaining the uniqueness constraint. The algorithm terminates because N gets strictly smaller with each step while remaining a natural number; and because for every N ≥ 1 there is a Fn ≤ N (because F1 = 1); and because the natural numbers are well-ordered by <.
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
On a similar note: Suppose you have a two-pan balance. What is the minimum number of weights you need to measure items of every integer weight from 1 to 40?
Proof: for a given number N. Find the greatest fibonacci number less than or equal to N; call this Fn. Now, N < Fn+1 = Fn-1+Fn, so N-Fn < Fn-1. Therefore, the algorithm can be repeated while only ever using strictly smaller fibonacci numbers, maintaining the uniqueness constraint. The algorithm terminates because N gets strictly smaller with each step while remaining a natural number; and because for every N ≥ 1 there is a Fn ≤ N (because F1 = 1); and because the natural numbers are well-ordered by <.
I'm not sure I understand that proof.
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
If that observation is correct, would it mean that every natural number can be written as the sum of unique even-index or odd-indexed fibonacci numbers?
On a similar note: Suppose you have a two-pan balance. What is the minimum number of weights you need to measure items of every integer weight from 1 to 40?
I can at least give an upper bound. If you use weights of powers of 2, then with 6 weights you can represent any value between 1 and 63 as a "binary number" using the weights.
I don't know, however, if when using 1-40 in particular, some other scheme would allow 5 weights to be used.
To try and clarify rhebus's reasoning:
Assume that all numbers less than F(n), the nth Fibonacci number, are the sum of distinct Fibonacci numbers. Now, this is also true for all numbers less than F(n+1), because all numbers K in the range F(n) < K < F(n+1) can be written as K = F(n) + k, where k < F(n) (which follows from the fact that each Fibonacci number is the sum of the last two), and hence since k is the sum of distinct Fibonacci numbers, so is K.
Hence if all numbers < F(n) are the sum of distinct Fibonacci numbers then the same is true for numbers < F(n+1). Hence all we need to do is verify this for the case n=1 (which is trivial) and the proof is complete.
I can at least give an upper bound. If you use weights of powers of 2, then with 6 weights you can represent any value between 1 and 63 as a "binary number" using the weights.
I don't know, however, if when using 1-40 in particular, some other scheme would allow 5 weights to be used.
You can easily lower the upper bound to 5 by ommiting the weight of value 1. You could only compare to even values, but if unknown weigth X is heavier than known weights Y and Y+2, X is obviously Y + 1.
The proof is based on contructing an algorithm to generate such a decomposition, proving the algorithm always picks unique fibonacci numbers, and proving it always terminates. It is a greedy algorithm, which is an algorithm which works by trying to take the biggest piece available at each stage. Making change for an amount of money is generally done by a greedy algorithm. Greedy algorithms don't always work for all problems, but for this problem, it works perfectly.
The algorithm-based proof operates "top down" because you start from a target number N and reduce the problem to a smaller problem of finding a decomposition for (N-Fn). (Note that N and n are different numbers; sorry about that. K would have been a better choice.) thatguy's proof is related but it's "bottom up" because it starts by proving a base case for 1 and proves each subsequent case by induction: the inductive step is "if it works for numbers < Fn, it will work for numbers < Fn+1".
I suspect my proof feels more natural to me because I'm a computer scientist by training, and I was thinking in terms of algorithms & termination; proof by induction feels like a more mathematics-style proof.
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
If that observation is correct, would it mean that every natural number can be written as the sum of unique even-index or odd-indexed fibonacci numbers?
Hmm, actually now I think I was wrong about that. If the algorithm picks Fn then it won't pick Fn-1; but there's nothing to stop it picking Fn-3. I guess there's a weaker statement: the algorithm won't pick two consecutive fibonacci numbers.
I can at least give an upper bound. If you use weights of powers of 2, then with 6 weights you can represent any value between 1 and 63 as a "binary number" using the weights.
I don't know, however, if when using 1-40 in particular, some other scheme would allow 5 weights to be used.
As you suspect, there is more to this problem. There are more configurations of weights in the scales than you have considered so far.
You can easily lower the upper bound to 5 by ommiting the weight of value 1. You could only compare to even values, but if unknown weigth X is heavier than known weights Y and Y+2, X is obviously Y + 1.
This wasn't quite what I had in mind; but I suppose according to the problem as stated, you could do that. You can do better than 5, though, and even get an exact weighing rather than inferring from multiple inexact weighings.
It's the simplest form of a greedy algorithm. You can generate a sequence of unique fibonacci numbers for your number N by picking the largest number F(n) <= N, then repeating for the remainder N-F(n), until nothing is left.
So for 100, you'd pick 89, remainder 11. Pick 8, remainder 3. Pick 3, nothing remains. Your unique sequence is 89, 8, 3.
To prove that this algorithm works, he needs to prove three things:
a) for every N > 0, there's always an F(n) <= N to pick. Since F(1) = 1, this is ok.
b) After you've subtracted your F(n) from N, the largest fibonacci number smaller than the remainder N-F(n) is not F(n) again, but a smaller fibonacci number. Otherwise they wouldn't be unique. He's proven that with all those intimidating subscripts; take a closer look.
c) The algorithm terminates. In every step, you subtract a positive number from your N, thus N will reach 0 eventually.
Not only has he proven that a sequence exists for every natural number N, he's given you an algorithm to find such a sequence. Constructive proofs ftw.
aaaand got ninja'd. ^^
rhebus wrote:
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
As you noticed, that's not true.
Counterexample: 10. Your algorithm yields 8+2 with indexes 6, 3.
Other valid sequences for 10 are 8+1+1 (index 6,2,1) or 5+3+2 (index 5,4,3) or 5+3+1+1 (index 5,4,2,1) - neither of these sequences' indexes have the same parity.
rhebus wrote:
What is the minimum number of weights you need to measure items of every integer weight from 1 to 40?
We'll need a weight of 1 (let's call it W1) to measure 1.
1 = W1
We can measure 2, 3 and 4 if we add W3.
2 + W1 = W3
3 = W3
4 = W3 + W1
The next one we'll need seems to be W9.
5 + W3 + W1 = W9
6 + W3 = W9
7 + W3 = W9 + W1
8 +W1 = W9
9 = W9
10 = W9 + W1
11 + W1 = W9 + W3
12 = W9 + W3
13 = W9 + W3 + W1
Last one is W27, I think you can figure out the way. 4 weights.
Hmm, actually now I think I was wrong about that. If the algorithm picks Fn then it won't pick Fn-1; but there's nothing to stop it picking Fn-3. I guess there's a weaker statement: the algorithm won't pick two consecutive fibonacci numbers.
So the original problem could be made slightly "harder" by phrasing it as: "Prove that every natural number can be written as the sum of unique, non-consecutive fibonacci numbers."
So the original problem could be made slightly "harder" by phrasing it as: "Prove that every natural number can be written as the sum of unique, non-consecutive fibonacci numbers."
Not really, not for my method of proof at least. Just replace this line:
K = F(n) + k, where k < F(n)
with this line:
K = F(n) + k, where k < F(n-1) (which still follows from F(n) = F(n-1) + F(n-2)), and the rest of the proof is the same.
What might be harder is proving that such a summation is, in fact, unique, ie there is exactly one way of expressing any integer as the sum of non-consecutive Fibonacci numbers. I have a feeling this would be the case for some reason but I can't prove it.
While we're on Fibonacci numbers, I remember my old maths teacher was very proud of being the first person to prove the following:
The only Fibonacci numbers which are also twin primes are 3, 5 and 13.
(A twin prime is a prime number that differs from another prime number by 2.)
He never showed us the proof, but it must have been relatively elementary for a proof discovered in the 80's because he never even did a master's. If anyone can find a proof, I'd be really happy indeed.
Also I guess the fact that elementary proofs keep popping up to solve age-old problems is hope for amateur mathematicians everywhere.
So the original problem could be made slightly "harder" by phrasing it as: "Prove that every natural number can be written as the sum of unique, non-consecutive fibonacci numbers."
Am I missing something obvious or is that not possible?
5 = 2 + 3
6 = 1 + 2 + 3
8 = 1 + 2 + 5
8 = 3 + 5
<Zurreco> if so called professional players cant adapt to every playing field, theyre obviously not that great
So the original problem could be made slightly "harder" by phrasing it as: "Prove that every natural number can be written as the sum of unique, non-consecutive fibonacci numbers."
Am I missing something obvious or is that not possible?
5 = 2 + 3
6 = 1 + 2 + 3
8 = 1 + 2 + 5
8 = 3 + 5
While we're on Fibonacci numbers, I remember my old maths teacher was very proud of being the first person to prove the following:
The only Fibonacci numbers which are also twin primes are 3, 5 and 13.
(A twin prime is a prime number that differs from another prime number by 2.)
He never showed us the proof, but it must have been relatively elementary for a proof discovered in the 80's because he never even did a master's. If anyone can find a proof, I'd be really happy indeed.
Also I guess the fact that elementary proofs keep popping up to solve age-old problems is hope for amateur mathematicians everywhere.
http://www.jstor.org/stable/2695779
American Mathematical Monthly (Vol. 109, No. 1, Jan., 2002), in the standard "Short Problem → Solution" section.
So the original problem could be made slightly "harder" by phrasing it as: "Prove that every natural number can be written as the sum of unique, non-consecutive fibonacci numbers."
This is related to the numerical base phinary: using the golden ratio as a number base (as opposed to an integer as in binary or decimal), you can come up with a representation of any integer using only digits 0 and 1 and never using the sequence 11.
There is a close relationship between the fibonacci numbers and the golden ratio: the ratio between consecutive fibonacci numbers (1/1, 2/1, 3/2, 5/3, 8/5 etc) asymptotically approaches the golden ratio; and the formula for the fibonacci numbers uses the golden ratio.
I think there's an easy way of demonstrating why you never need consecutive fibonacci numbers.
If in your sum there are two consecutive fibonacci numbers, let's say F(n) and F(n+1), you can replace those two terms with, by definition, F(n+2). You can keep doing this recursively until there are no consecutive pairs. The result of the sum doesn't change.
Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo
The existence of such a representation is not so difficult to imagine once you know any integer can be written as the sum of distinct Fibonacci numbers, as you can see that the densest sum F(2)+F(3)+F(4)+F(5)+F(6)+F(7)+... can change into F(4)+F(6)+F(8)+... as desired. The proof of the uniqueness, however, is a little formal since it often requires a non-constructive argument. That's the way of mathematics. :) I'm looking forward to seeing how people prove it.
Retired because of that deletion event.
Projects (WIP RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"
