[superprismatic]

Here's something I came across in my mathematical perusals:

0   1   1   2   3   5   8  13 ...

1   3   4   7  11  18  29  47 ...

2   4   6  10  16  26  42  68 ...

...etc...

[/code]


Notice that each row above is fibonacci in that, except for

the first two columns, a number in the i[sup]th[/sup] column is the sum

of the numbers in the (i-1)[sup]st[/sup] and (i-2)[sup]nd[/sup] columns.

Also notice that the first column is just the one-up integers

starting at 0.

 

Here's how to generate the rest of the array:

Label the columns -1,0,1,2,3,...  The first row is the usual

fibonacci sequence.  We will genetate the rows consecutively

beginning 1, 2, 3, etc.  For the row beginning with N, we

look for N in columns labeled with [i]positive[/i] integers and

in the rows above the one we are generating.   When we find

N in this manner, we take the number immediately to its right,

add 1 to it, and put this next to N in the line we are generating.

Then we generate the rest of the row using the fibonacci rule

 

For example, to genetate the row beginning with 1, we find

the 1 in the column labeled 1 and take the 2 immediately to

the right of it, add 1 to it to get 3.  That 3 becomes the

number next to the 1 in the line we are generating.

 

Another example:  The row which begins 3.  We find a 3 in the

top row with a 5 next to it.  We add 1 to the 5 to get the 6

as the element in the 0[sup]th[/sup] column of the row beginning with 3.

Using the fibonacci rule, we find that row to be:

[code]

3   6   9  15  24  39  63 102 ...

The claim was made that every positive integer can be found in

one, and only one, positive integer labeled column and

one, and only one, row of this array. Can you prove this?

[Guest]

took me a bit to understand what you were getting at.

so the -1 column is the counting numbers, and the 0 column is the N+1 Fibonacci number, +1.

after that each row follows the Fibonacci rule. i think this property would be true with any exponential sequence.

take the *2 sequence.

0 1 2 3 4 5 6 <- column #

1 2 4 8 16 32 64...

3 6 12 24 48..

5 10 20 40 80..

7 14 28 56...

if you continue in this fashion, its clear that no numbers will be missed, since any number can be expressed as 2^n *an odd number. also it's quite clear that no number will be hit more than once, since every number has a unique prime factoring.

Edited September 24, 2011 by phillip1882

[CaptainEd]

Superprismatic, I wanted to post an expression of my pleasure with this puzzle, but I thought I'd wait until I had something constructive to help in its solution. Unfortunately, I can't see deep enough yet to meet the latter goal. So thank you for the puzzle, such a bizarre construction and a fascinating result. (...I'll keep on thinking...)

[superprismatic]

Superprismatic, I wanted to post an expression of my pleasure with this puzzle, but I thought I'd wait until I had something constructive to help in its solution. Unfortunately, I can't see deep enough yet to meet the latter goal. So thank you for the puzzle, such a bizarre construction and a fascinating result. (...I'll keep on thinking...)

Join the club. I haven't been able to prove it either. I'm glad you enjoy the puzzle. Thanks for the feedback!

[Guest]

unfortunately, it's not true.

0   1   1   2   3   5   8  13  21

1   3   4   7  11 18 29 47 76

2   4   6  10 16 26 42 68 110

3   6   9  15 24 39 63 102 165

4  9  13 22 35 57 92  149 241 

as you can see, it is indeed the case some numbers are hit more than once, and some numbers are never hit. (13 gets hit twice, and 12 will never be hit.)

Edited October 5, 2011 by phillip1882

[CaptainEd]

Phillip1882, I can't read your spoiler, but I've got to believe you've not understood the instructions. Here are the first few rows and columns, as I understand the task--12 appears once, 13 appears once, in contrast to your claim:

  [font=courier new,courier,monospace

  -1   0   1   2   3   4   5   6

    0   1   1   2   3   5   8  13

	1   3   4   7  11  18  29  47

	2   4   6  10  16  26  42  68

	3   6   9  15  24  39  63 102

	4   8  12  20  32  52  84 136

	5   9  14  23  37  60  97 157

	6  11  17  28  45  73 118 191

	7  12  19  31  50  81 131 212

	8  13  22  36  58  94 152 246

	9  15  25  41  66 107 173 280

   10  17  27  44  71 115 186 301

   11  19  30  49  79 128 207 335

   12  21  33  54  87 141 228 369

   13  22  35  57  92 149 241 390   [/font]

Edited October 5, 2011 by CaptainEd

[CaptainEd]

Sigh, some days I can't use this editor...

  -1   0   1   2   3   4   5   6

   0   1   1   2   3   5   8  13

   1   3   4   7  11  18  29  47

   2   4   6  10  16  26  42  68

   3   6   9  15  24  39  63 102

   4   8  12  20  32  52  84 136

   5   9  14  23  37  60  97 157

   6  11  17  28  45  73 118 191

   7  12  19  31  50  81 131 212

   8  13  22  36  58  94 152 246

   9  15  25  41  66 107 173 280

  10  17  27  44  71 115 186 301

  11  19  30  49  79 128 207 335

  12  21  33  54  87 141 228 369

  13  22  35  57  92 149 241 390[/font]

[font=courier new,courier,monospace]

[EventHorizon]

unfortunately, it's not true.

0   1   1   2   3   5   8  13  21

1   3   4   7  11 18 29 47 76

2   4   6  10 16 26 42 68 110

3   6   9  15 24 39 63 102 165

4  9  13 22 35 57 92  149 241

as you can see, it is indeed the case some numbers are hit more than once, and some numbers are never hit. (13 gets hit twice, and 12 will never be hit.)

You misunderstood the method of choosing the elements of the column marked '0'

It is not simply the fibonacci numbers plus one.

For instance, the row starting with 4 would require you to find the 4 in the columns with positive integers. It occurs in the column marked '1' and in the row beginning with 1. To the right of that is a 7, so adding 1 to that makes it an 8, not 9 (the fibonacci+1). The next number on that row happens to be the 12 that wouldn't occur anywhere if choosing fib+1.

[Guest]

alright sorry guys, you're right of course...

Sigh, some days I can't use this editor...

i feel your pain captainEd

[Guest]

column 0 seems to alternate between adding 2 and adding 1 in the form of the fibinocci word.

1

2

21

212

21221

21221212

2122121221221

212212122122121221212

the sequence of additions for column 0...

1 3 4 6 8 9 11 12 14 16 17 19 21 22 24 25 27 29...

2 1 2 2 1 2  1  2  2  1  2  2  1  2  1  2  2...

Edited October 5, 2011 by phillip1882

[EventHorizon]

I could have been more rigorous in a number of spots, but I think the main idea is sound. Thoughts?

First, I'll change the representation from the matrix one given to a graph one that makes things clearer to me.

Nodes in the graph, which are equivalent to the numbers in the matrix in the positive numbered columns, are organized into columns themselves.

There are two types of links between nodes, solid and dashed. The solid ones have a value of 0 and the dashed have a value of 1.

The first column contains a single node labeled 1. This is linked to the next column with a solid link to a node labeled 2.

Solid links represent that that node was made by the addition of the two previous nodes (and the links between them, but solid links are valued as 0). The dashed link is for the case of what would be a new row in the matrix representation. There can only be a dashed link from a node that was linked to with a solid link.

At this point I'll give a definition and prove a few lemmas.

Definition for a fibonacci sequence: For given a and b,

* fib(a,b,0) = a

* fib(a,b,1) = b

* fib(a,b,n) = fib(a,b,n-1) + fib(a,b,n-2)

Example: fib(0,1,n) is the regular fibonacci numbers as n increases.

Lemma 1: fib(a+c,b+d,n) = fib(a,b,n) + fib(c,d,n)

Proof: For n=0, a+c = fib(a+c,b+d,0) = fib(a,b,0) + fib(c,d,0) = a+c

For n=1, b+d = fib(a+c,b+d,1) = fib(a,b,1) + fib(c,d,1) = b + d

For n>1: Assume it is true for all values of values up to n-1.

fib(a+c,b+d,n-1) = fib(a,b,n-1) + fib(c,d,n-1)

fib(a+c,b+d,n-2) = fib(a,b,n-2) + fib(c,d,n-2)

Adding the above two lines gives

fib(a+c,b+d,n-1) + fib(a+c,b+d,n-2) = fib(a,b,n-1) + fib(a,b,n-2) + fib(c,d,n-1) + fib(c,d,n-2)

fib(a+c,b+d,n) = fib(a,b,n) + fib(c,d,n)

Done!

Lemma 2: For all non-negative integers n, fib(a+1,b+1,n) - 1 = fib(a,b,n) + Sum_i=1^floor(n/2) fib(1,2,n-2i)

Proof: For n=0, a = a+1 - 1 = fib(a+1,b+1,0) - 1 = fib(a,b,0) + Sum_i=1^floor(0/2) fib(1,2,0-2i) = a + Sumi=₁⁰ (doesn't matter) = a

For n=1, b = b+1 - 1 = fib(a+1,b+1,1) - 1 = fib(a,b,1) + Sum_i=1^floor(1/2) fib(1,2,1-2i) = b + Sum_i=1⁰ (doesn't matter) = b

For n>1, fib(a,b,n) + Sum_i=1^floor(n/2) fib(1,2,n-2i) =

fib(a,b,n) + fib(1,2,n-2) + fib(1,2,n-4) + ... + fib(1,2,2 or 3) + fib(1,2,0 or 1) =

fib(a,b,n) + fib(1,2,n-2) + fib(1,2,n-4) + ... + fib(1,2,2 or 3) + fib(1,2,0 or 1) + 1 - 1 =

fib(a,b,n) + fib(1,2,n-2) + fib(1,2,n-4) + ... + fib(1,2,2 or 3) + fib(1,2,1 or 2) - 1 =

fib(a,b,n) + fib(1,2,n-2) + fib(1,2,n-4) + ... + fib(1,2,3 or 4) - 1 =

...

fib(a,b,n) + fib(1,2,n-2) + fib(1,2,n-4) + fib(1,2,n-5) - 1 =

fib(a,b,n) + fib(1,2,n-2) + fib(1,2,n-3) - 1 =

fib(a,b,n) + fib(1,2,n-1) - 1 =

fib(a,b,n) + fib(1,1,n) - 1 =

fib(a+1,b+1,n) - 1

Done!

Lemma 3: given fib(a,b,n) <= x < fib(a,b,n+1) and fib(a,b,n+1) <= y <= fib(a,b,n+2), then fib(a,b,n+2) <= x+y < fib(a,b,n+3)

This is simple enough I won't give a proof (I'd have called it a numbered equation, but I thought I'd keep it consistent).

It's obvious that the quickest way to increase node values is to alternatively follow solid and dashed links (the most dashed links you can for as much "+1" as possible).

Using Lemma 3 and Lemma 2 with a=2 and b=3, we can see that the values in each column are bounded below by a fibonacci number, and above by one less than a fibonacci number.

Assume we start keeping track at an arbitrary point labeled node a.

As shown in the image above, at the first branch you get the pairs (b, a+b) and (b+1, a+b+1) (b+1 by adding the value of the dashed link to the first node).

By lemma 2, if the greater of the two pairs only follows solid links (slowest growth), it will always be 1 greater than following alternatively solid and dashed links starting with the lower valued path when comparing nodes in the same column.

Repeating this find at all equivalent locations shows all values in a column will be unique (since a and b are positive integers).

Now we need to simply show that the number of elements in each column is enough to represent each integer in the range of a fibonacci number up to, but not including, the next fibonacci number.

First, notice that each node creates a solid link to a new node the next column (the next number in the same row in the matrix representation) as well as a dashed link from next column to a new node in the column after that (a new row in the matrix representation).

What this means is that for each node in a given column, there is a new node in both the next two columns. Both the first and the second columns have 1 node each. since they both add to the number of nodes in the third, there's 2 in the third. Obviously, this is the same additive rule as the fibonacci numbers.

Since there are just enough nodes to represent each integer from one fibonacci number to the next in a given column, they are all unique, and this follows indefinitely, each integer is represented as a node's value exactly once in the graph (and therefore the matrix too).