|
Stated below are a few challenging problems. If you are first to publish a solution, let me know, and collect your reward!
|
|
The sequence originates in
William Kolakoski, "Self generating runs, Problem 5304," American Mathematical Monthly 72 (1965) 674. For a proof that the Kolakoski sequence is not periodic, see the same Monthly 73 (1966) 681-682.
See also Kolakoski Sequence (Eric Weisstein's The World of Mathematics)
2. A Shuffle. Is every positive integer a term of this sequence:
1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46, . . . ?
Reward: $300.00. To see how to generate the sequence, visit
Kimberling Sequence (Eric Weisstein's The World of Mathematics).
For a discussion and variant of the problem, see
Richard K. Guy, Unsolved Problems in Number Theory, second edition, Springer-Verlag, 1994.
The problem originates in
C. Kimberling, Problem 1615, Crux Mathematicorum 17 (1991) 44.
3. Repetition-resistant sequence. Reward: $100.00.
Consider the sequence (or infinite word)
R = (r1, r2, r3, . . . ) = 010001101011100100111101100000101... (commas deleted).
The first segment of length 1 to repeat is "0", at r1 and r3.
The first segment of length 2 to repeat "00", at r5.
The first segment of length 3 to repeat is "010", at r10.
The sequence R is constructed to avoid repetitions "as long as possible", as follows:
rn+1 = 1 if and only if
(r1, r2, . . . , rn, 0), but not (r1, r2, . . . , rn, 1),
has greater maximal repeated segment length than
(r1, r2, . . . , rn) has.
A finite string of 0's and 1's is called a word. Does every word occur in R?
If so, then it is easy to see that every word repeats infinitely many times in R, which is notable, since the rule for generating R tries to resist repetition.
This problem originates, in more general form, in
C. Kimberling, Problem 2289, Crux Mathematicorum 23 (1997) 501; [no solutions received: 24 (1998) 525].
The problem has been solved in the affirmative: the binary word R does indeed contain every binary word infinitely many times. The word R corresponds to a choice-sequence consisting of all 0's. Any binary sequence can serve as a choice-sequence; details are given in the reference cited just above. To see hundreds of terms in the repetition-resistant sequence determined by your choice of choice-sequences, visit Alejandro's Dau's interactive Java generator,
Secuencia Maximizadora de Subcadenas
The solution appears in Crux Mathematicorum 29 (2003) 320-321.
4. A Hard Count. Reward: $100.00. Like the theory of relativity, this problem has a special version and a general version. The special case originates in
C. Kimberling, Problem 2386, Crux Mathematicorum 24 (1998) 426 and is equivalent to the following:
Write "1". Skip some space and count the one 1 you've written by writing "1 1". Skip some more space and count the three 1's you've written so far by writing "3 1" - except write it with 3 above 1, like this:
3
1.
Skip some space, and count the four 1's and one 3 that you've written so far by writing
4 1
1 3.
Skip some space, and count what you've written so far by writing
6 2 1
1 3 4.
Skip some space, and count what you've written so far by writing
8 1 3 2 1
1 2 3 4 6.
If this procedure continues indefinitely, will every positive integer eventually be written?
Now for the general form of this problem. It's just like the special, except that we start with an arbitrary initial counting; that is, instead of starting with one 1, start with
a(1) a(2) a(3) . . . a(n)
b(1) b(2) b(3) . . . b(n),
where all the a(i) and b(i) are positive integers, and the b(i) are distinct. The problem is to prove or disprove that every positive integer will eventually be written during the counting procedure.
5. The MD Problem (M=Multiply, D=Divide). Reward: $100.00.
Let a1 = 1, and for n > 1, define an = [an-1/2] if this number is not in the set {0, a1, . . . , an-1}, and an = 3an-1 otherwise.
Does every positive integer occur exactly once in this sequence?
The problem originates in
C. Kimberling, Problem 2248, Crux Mathematicorum 26 (2000) 238; [no solutions received: 27 (2001) 345].
In the statement of the problem, the notation [x] means "the greatest integer that is <= x". Thus, the sequence (an) is generated by repeatedly multiplying by 3 and dividing by 2.
The MD sequence defined above begins like this: 1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, . . .
You can obtain another MD sequence by using 2 as multiplier and 3 as divisor:
1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 96, 32, 64, 21, 7, 14, 28, 9, 18, 36, . . .
Or, let m and d be any two relatively prime integers greater than 1. Does the resulting MD sequence contain every positive integer exactly once?
Mateusz Kwasnicki of Wroclaw University of Technology solved the MD problem in general and in the affirmative. See Crux Mathematicorum 30 (2004) 235-239.
6. Are They All Even? Reward: $50.00.
Begin an array by writing the Fibonacci numbers: 1, 1, 2, 3, 5, 8, ... Start row 2 with the least unused positive integer, which is 4; follow 4 by 6, and finish the row using the Fibonacci recurrence (i.e., add the two most recent numbers to produce the next, so that row 2 starts with 4, 6, 10, 16, 26, 42). Start row 3 with the least unused, which is 7, follow 7 by 12, and then use the recurrence to produce 19, 31,.... Continue in this manner (the choice of second term in each new row is revealed below), getting rows 1 to 4 starting like this:
1 2 3 5 8 13 . . .
4 6 10 16 26 42 . . .
7 12 19 31 50 81 . . .
9 14 23 37 60 97 . . .
.
.
.
Here is the recipe for the second number in each row: let r be the golden ratio, (1+sqrt(5))/2, let i be the number of the row, and let x be the first number in the row; then the second number is [rx] if i is even, and it is [rx]+1 if i is odd.
For example, row 5 starts with the least unused, which is x=11, and this is followed by [11r]+1, which is 18.
Is every number is column 2 even?
In anticipation that the answer is yes, the array is introduced as the Even Second Column Array in
C. Kimberling, "The First Column of an Interspersion," The Fibonacci Quarterly 32 (1994) 301-315.