Difference between revisions of "Human proof that completely multiplicative sequences have discrepancy greater than 2"

From Polymath1Wiki
Jump to: navigation, search
m
Line 1: Line 1:
It is [[multiplicative sequences|known from computer search]] that the longest completely multiplicative sequence <math>f: [N] \to \{-1,+1\}</math> of discrepancy 2 has length 246.  Here we record the attempts to prove this by hand.  Notation: we display our function in rows of 10, starting with 0.  We use the notation that + and - denote values which are known to equal +1 or -1 respectively, and ? for unknown values.  I'll also put a bar | after the last place where it is known that f(1)+...f(n) sums to 0; these can only occur after an even number, and will be automatic in the middle of any ++++ or ---- string.  Thus, initially our array looks like this:
+
It is [[multiplicative sequences|known from computer search]] that the longest completely multiplicative sequence <math>f: [N] \to \{-1,+1\}</math> of discrepancy 2 has length 246.  Here we record the attempts to prove this by hand.  Notation: we display our function in rows of 10, starting with 0.  We use the notation that + and - denote values which are known to equal +1 or -1 respectively, and ? for unknown values.  Thus, initially our array looks like this:
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 9: Line 9:
  
 
since f(n^2) = 1 for all square numbers.
 
since f(n^2) = 1 for all square numbers.
 +
 +
The notions of a ''cut'' and a ''block'' will be useful.  A ''cut'' occurs between n and n+1 whenever it can be proved that f[1,n] sums to 0; these can only occur when n is even.  We indicate a cut by a bar | between n and n+1.  Thus for instance we begin with just one cut:
 +
 +
0 1 2 3 4 5 6 7 8 9
 +
 +
0|+ ? ? + ? ? ? ? +  0-9
 +
? ? ? ? ? ? + ? ? ?  10-19
 +
? ? ? ? ? + ? ? ? ?  20-29
 +
? ? ? ? ? ? + ? ? ?  30-39
 +
 +
A ''block'' is any interval between two cuts; thus inside each block one must sum to zero, and the discrepancy inside each block is at most 2.  Thus we can "localise" the analysis to each block, though multiplicativity relates the blocks together.
 +
 +
A block is ''solved'' if all values are assigned in it.  Solved blocks are uninteresting (other than for the values they provide by multiplicativity), so we shall adopt the convention of concatenating solved blocks with adjacent blocks to reduce clutter.
 +
 +
More notation: we use f[a,b] as short for f(a)+...+f(b).  Note that
 +
 +
: f[a,b] = -4,-2,0,2,4 if a is odd and b is even;
 +
: f[a,b] = -3,-1,1,3 if a and b are both odd or both even;
 +
: f[a,b] = -2,0,2 if a is even and b is odd.
 +
 +
Also if [a,b] starts or ends at a cut, then f[a,b] has magnitude at most 2.
 +
 +
A key observation is that if f(2n)=f(2n+1) then there must be a cut between 2n and 2n+1.
 +
 +
== Case 1. f(2)=1 ==
  
 
Now, let us '''assume''' f(2)=1 and that the discrepancy is at most 2 and see what happens.  From multiplicativity we obtain f(2n^2)=1, thus
 
Now, let us '''assume''' f(2)=1 and that the discrepancy is at most 2 and see what happens.  From multiplicativity we obtain f(2n^2)=1, thus
Line 19: Line 44:
 
  ? ? + ? ? ? + ? ? ?  30-39
 
  ? ? + ? ? ? + ? ? ?  30-39
  
and then by using discrepancy we get f(3)=f(5)=-1, thus
+
As f(8)=f(9) we can now cut at 8=9.  And then by using discrepancy we get f(3)=f(5)=-1, thus
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
 
   
 
   
  0|+ + - + - ? ? + +  0-9
+
  0|+ + - + - ? ? +|+  0-9
 
  ? ? ? ? ? ? + ? + ?  10-19
 
  ? ? ? ? ? ? + ? + ?  10-19
 
  ? ? ? ? ? + ? ? ? ?  20-29
 
  ? ? ? ? ? + ? ? ? ?  20-29
 
  ? ? + ? ? ? + ? ? ?  30-39
 
  ? ? + ? ? ? + ? ? ?  30-39
  
which then by multiplicativity extends to
+
which then by multiplicativity and adding cuts where obvious extends to
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
 
   
 
   
  0 + + - + - -|? + +  0-9
+
  0 + + - + - -|? +|+  0-9
  - ? - ? ? + + ? + ?  10-19
+
  -|? - ? ? + + ? + ?  10-19
 
  - ? ? ? - + ? - ? ?  20-29
 
  - ? ? ? - + ? - ? ?  20-29
 
  + ? + ? ? ? + ? ? ?  30-39
 
  + ? + ? ? ? + ? ? ?  30-39
  
Looking at f(1)+...+f(9) we see that f(7) is forced to be -1; from this and multiplicativity, and showing rows up to 100, we arrive at
+
Looking at the 7-8 block we see that f(7) is forced to be -1; from this and multiplicativity, and showing rows up to 100, we arrive at
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 53: Line 78:
 
  -
 
  -
  
This seems to be about as far as one can get just from the assumption f(2)=+1. 
+
Note that
 +
 
 +
: f[15,19] = 3 + f(17) + f(19)
 +
 
 +
cannot exceed 3, and
 +
 
 +
: f[168,171] = 2 - f(17) + f(19)
  
Let's write f(11)=a, f(13)=b, f(17)=c, f(19)=d, f(23)=e, f(29)=f and A = -a, B = -b, C = -c, D=-d, E=-e, F=-fThen we can fill in more:
+
cannot exceed 2.  Thus f(19) = -1We use this information to update the board:
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
 
   
 
   
 
  0 + + - + - - - + +  0-9
 
  0 + + - + - - - + +  0-9
  -|a - b - + + c + d   10-19
+
-|? - ? - + + ? + -  10-19
 +
- + ? ? - + ? - - ?  20-29
 +
+ ? + ? ? + + ? - ?  30-39
 +
- ? + ? ? - ? ? - +  40-49
 +
+ ? ? ? - ? - + ? ?  50-59
 +
+ ? ? ? + ? ? ? ? ?  60-69
 +
+ ? + ? ? - - ? ? ?  70-79
 +
- + ? ? ? ? ? ? ? ?  80-89
 +
- ? ? ? ? + - ? + ?  90-99
 +
-
 +
 
 +
Let's write f(11)=a, f(13)=b, f(17)=c, f(23)=e, f(29)=f and A = -a, B = -b, C = -c, E=-e, F=-f.  Then we can fill in more:
 +
 
 +
0 1 2 3 4 5 6 7 8 9
 +
 +
0 + + - + - - - + +  0-9
 +
  -|a - b - + + c + -   10-19
 
  - + a e - + b - - f  20-29
 
  - + a e - + b - - f  20-29
  + ? + A c + + ? d B  30-39
+
  + ? + A c + + ? - B  30-39
 
  - ? + ? a - e ? - +  40-49
 
  - ? + ? a - e ? - +  40-49
  + C b ? - A - D f ?  50-59
+
  + C b ? - A - + f ?  50-59
 
  + ? ? - + B A ? c E  60-69
 
  + ? ? - + B A ? c E  60-69
  + ? + ? ? - d A B ?  70-79
+
  + ? + ? ? - - A B ?  70-79
 
  - + ? ? + C ? F a ?  80-89
 
  - + ? ? + C ? F a ?  80-89
  - B C ? ? D - ? + a  90-99
+
  - B C ? ? + - ? + a  90-99
 
  -
 
  -
  
The most profitable '''assumption''' here seems to be f(37)=+1.  This forces f(1)+...+f(37) to equal +1, which then forces f(34)=-1 and then f(33)=-1 also.  Filling in these values gives
+
This seems to be about as far as one can get just from the assumption f(2)=+1. 
 +
 
 +
== Case 1.a f(2)=f(37)=1 ==
 +
 
 +
The most profitable '''assumption''' here seems to be f(37)=+1.  This creates a cut at 36-37, which then forces f(34)=-1 and then f(33)=-1 also.  Filling in these values and adding in cuts gives
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
 
   
 
   
 
  0 + + - + - - - + +  0-9
 
  0 + + - + - - - + +  0-9
  - + -|b - + + - + d   10-19
+
  - + -|b - + + - + -   10-19
 
  - + + e - + b - - f  20-29
 
  - + + e - + b - - f  20-29
  + ? + - - + + + d B  30-39
+
  + ? +|- - + +|+ - B  30-39
 
  - ? + ? + - e ? - +  40-49
 
  - ? + ? + - e ? - +  40-49
  + + b ? - - - D f ?  50-59
+
  + + b ? -|- - + f ?  50-59
 
  + ? ? - + B - ? - E  60-69
 
  + ? ? - + B - ? - E  60-69
  + ? + ? + - d - B ?  70-79
+
  + ? + ? + - -|- B ?  70-79
  - + ? ? + + ? F + ?  80-89
+
  - + ? ? +|+ ? F + ?  80-89
  - B + ? ? D - ? + +  90-99
+
  - B + ? ? + - ? + +  90-99
 
  -
 
  -
  
looking at f(30)+...+f(37) we thus have f(31)=-1,
+
looking at f[30,32] we thus have f(31)=-1,
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
 
   
 
   
 
  0 + + - + - - - + +  0-9
 
  0 + + - + - - - + +  0-9
  - + -|b - + + - + d   10-19
+
  - + -|b - + + - + -   10-19
 
  - + + e - + b - - f  20-29
 
  - + + e - + b - - f  20-29
  + - + - - + + + d B  30-39
+
  +|- + - - + +|+ - B  30-39
 
  - ? + ? + - e ? - +  40-49
 
  - ? + ? + - e ? - +  40-49
  + + b ? - - - D f ?  50-59
+
  + + b ? -|- - + f ?  50-59
 
  + ? - - + B - ? - E  60-69
 
  + ? - - + B - ? - E  60-69
  + ? + ? + - d - B ?  70-79
+
  + ? + ? + - -|- B ?  70-79
  - + ? ? + + ? F + ?  80-89
+
  - + ? ? +|+ ? F + ?  80-89
  - B + + ? D - ? + +  90-99
+
  - B +|+ ? + - ? + +  90-99
 
  -
 
  -
  
from f(1)+...+f(19) we have b+d <= 0, while from f(35)+...+f(39) we have d-b <= 0.  Thus d must be -1:
+
== Case 1.a.1 f(2)=f(37)=f(13)=1 ==
  
0 1 2 3 4 5 6 7 8 9
 
 
0 + + - + - - - + +  0-9
 
- + -|b - + + - + -  10-19
 
- + + e - + b - - f  20-29
 
+ - + - - + + + - B  30-39
 
- ? + ? + - e ? - +  40-49
 
+ + b ? - - - + f ?  50-59
 
+ ? - - + B - ? - E  60-69
 
+ ? + ? + - - - B ?  70-79
 
- + ? ? + + ? F + ?  80-89
 
- B + + ? + - ? + +  90-99
 
-
 
  
 
Now suppose we '''assume''' b=+1.  Then by looking at f(1)+...+f(23) we have e=-1, and by looking at f(1)+...+f(37) we then have f=-1, leaving us with
 
Now suppose we '''assume''' b=+1.  Then by looking at f(1)+...+f(23) we have e=-1, and by looking at f(1)+...+f(37) we then have f=-1, leaving us with
Line 128: Line 166:
 
  + - + - - + + + -|-  30-39
 
  + - + - - + + + -|-  30-39
 
  - ? + ? + - - ? - +  40-49
 
  - ? + ? + - - ? - +  40-49
  + + + ? - - - + - ?  50-59
+
  +|+ + ? -|- - + - ?  50-59
 
  + ? - - + - - ? - +  60-69
 
  + ? - - + - - ? - +  60-69
 
  + ? + ? + - -|- - ?  70-79
 
  + ? + ? + - -|- - ?  70-79
  - + ? ? + + ? + + ?  80-89
+
  - + ? ? +|+ ? + + ?  80-89
  - - + + ? + - ? + +  90-99
+
  -|- +|+ ? + - ? + +  90-99
 
  -
 
  -
  
from f(1)+...+f(41) we have f(41)=+1, and from f(75)+...+f(79) we have f(79)=+1, and from f(84)+...+f(88) we have f(86)=-1, hence f(43)=-1:
+
from f[39,41] we have f(41)=+1, and from f[77,79] we have f(79)=+1, from f[51,54] we have f(53)=-1, from f[47,50] we have f(47)=-1, and from f[85,88] we have f(86)=-1, hence f(43)=-1:
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 143: Line 181:
 
  - + + - - + + - - -  20-29
 
  - + + - - + + - - -  20-29
 
  + - + - - + + + - -  30-39
 
  + - + - - + + + - -  30-39
  - + + - +|- - ? - +  40-49
+
  - + + - +|- - - - +  40-49
  + + + ? - - - + - ?  50-59
+
  + +|+ - - - - + - ?  50-59
 
  + ? - - + - - ? - +  60-69
 
  + ? - - + - - ? - +  60-69
 
  + ? + ? + - -|- - +  70-79
 
  + ? + ? + - -|- - +  70-79
Line 151: Line 189:
 
  -
 
  -
  
from f(81)+...+f(85) we must have f(83)=-1, and from f(81)+...+f(89) we must have f(89)=-1, and from f(1)+...+f(47) we have f(47)=+1, hence f(94)=-1:
+
But this creates a contradiction at the block [45,51]. Thus this case is impossible.
  
0 1 2 3 4 5 6 7 8 9
+
== Case 1.a f(2)=f(37)=1 ==
  
0 + + - + - - - + +  0-9
+
We have thus concluded in this case that f(13)=-1:
- + - + - + + - + -  10-19
+
- + + - - + + - - -  20-29
+
+ - + - - + + + - -  30-39
+
- + + - + - - + - +  40-49
+
+|+ + ? - - - + - ?  50-59
+
+ ? - - + - - ? - +  60-69
+
+ ? + ? + - -|- - +  70-79
+
- + + - + + - + + -  80-89
+
- - +|+ + + - ? + +  90-99
+
-
+
 
+
But this creates a contradiction at 95, we cannot have three +++ after a |.  So we conclude (under the assumptions f(2)=+1 and f(37)=+1) that b=-1:
+
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 173: Line 199:
 
  0 + + - + - - - + +  0-9
 
  0 + + - + - - - + +  0-9
 
  - + - - - + + - + -  10-19
 
  - + - - - + + - + -  10-19
  - + +|e - + - - - f  20-29
+
  - + +|e - + -|- - f  20-29
  + - + - - + + + - +  30-39
+
  +|- + - - + +|+ - +  30-39
  - ? + ? + - e ? - +  40-49
+
  -|? + ? + - e ? - +  40-49
  + + - ? - - - + f ?  50-59
+
  +|+ - ? -|- - + f ?  50-59
  + ? - - + + - ? - E  60-69
+
  + ? -|- + + -|? - E  60-69
  + ? + ? + - - - + ?  70-79
+
  + ? + ? + - -|- + ?  70-79
  - + ? ? + + ? F + ?  80-89
+
  - + ? ? +|+ ? F + ?  80-89
  - + + + ? + - ? + +  90-99
+
  - + +|+ ? + - ? + +  90-99
 
  -
 
  -
  
From f(1)+...+f(29) we have e=+1 and f=+1.  Looking at f(91)+...+f(95) we see that f(94)=-1 hence f(47)=+1, and we have a cut at 92-93, hence also at 96-97:
+
From the [23,26] and [27,30] blocks we have e=+1 and f=+1; from the block [51,54] we have f(53)=+1. Looking at [93,95] we see that f(94)=-1 hence f(47)=+1, and we have a cut at 92-93, hence also at 96-97:
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 191: Line 217:
 
  - + + + - + - - - +  20-29
 
  - + + + - + - - - +  20-29
 
  + - + - - + + + - +  30-39
 
  + - + - - + + + - +  30-39
  -|? + ? + - + - - +  40-49
+
  -|? + ? +|- + - - +  40-49
  + + - ? - - - + + ?  50-59
+
  + + - + - - - + +|?  50-59
  + ? - - + + - ? - -  60-69
+
  + ? -|- + + -|? - -  60-69
  + ? + ? + - - - + ?  70-79
+
  + ? + ? + - -|- +|?  70-79
  - + ? ? + + ? - + ?  80-89
+
  - + ? ? +|+ ? - + ?  80-89
 
  - + +|+ - + -|? + +  90-99
 
  - + +|+ - + -|? + +  90-99
 
  -
 
  -
  
from f(91)+...+f(99) we have f(97)=-1.  From the f(75)+...+f(77) chain we must have a cut at 76-77, hence also at 78-79:
+
from f[97,99] we have f(97)=-1.  From the [41,44] block we have f(41)=f(43)=-1:
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 207: Line 233:
 
  - + + + - + - - - +  20-29
 
  - + + + - + - - - +  20-29
 
  + - + - - + + + - +  30-39
 
  + - + - - + + + - +  30-39
  -|? + ? + - + - - +  40-49
+
  - - + - + - + - - +  40-49
  + + - ? - - - + + ?  50-59
+
  + + - + - - - + +|?  50-59
  + ? - - + + - ? - -  60-69
+
  + ? -|- + + -|? -|-  60-69
 
  + ? + ? + - -|- +|?  70-79
 
  + ? + ? + - -|- +|?  70-79
  - + ? ? + + ? - + ?  80-89
+
  - + - ? +|+ - - +|?  80-89
 
  - + +|+ - + - - + +  90-99
 
  - + +|+ - + - - + +  90-99
 
  -|
 
  -|
  
Any time we have two repeated signs at an even number followed by an odd number, there must be a cut in between, so we have a few more cuts to put in here:
+
Using the cuts we can fill in f(67)=+1 and f(89)=-1:
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 223: Line 249:
 
  - + + + - + - - - +  20-29
 
  - + + + - + - - - +  20-29
 
  + - + - - + + + - +  30-39
 
  + - + - - + + + - +  30-39
  -|? + ? + - + - - +  40-49
+
  - - + - + - + - - +  40-49
+|+ - ? - - - + + ?  50-59
+
+ ? -|- +|+ - ? -|-  60-69
+
+|? + ? + - -|- +|?  70-79
+
- + ? ? +|+ ? - + ?  80-89
+
- + +|+ - + - - + +  90-99
+
-|
+
 
+
Using the cuts we can fill in f(67)=+1 and f(86)=f(89)=-1, hence f(43)=-1:
+
 
+
0 1 2 3 4 5 6 7 8 9
+
 
+
0 + + - + - - - + +  0-9
+
- + - - - + + - + -  10-19
+
- + + + - + - - - +  20-29
+
+ - + - - + + + - +  30-39
+
-|? + - + - + - - +  40-49
+
 
  +|+ - ? - - - + + ?  50-59
 
  +|+ - ? - - - + + ?  50-59
 
  + ? -|- + + - + - -  60-69
 
  + ? -|- + + - + - -  60-69
 
  +|? + ? + - -|- +|?  70-79
 
  +|? + ? + - -|- +|?  70-79
  - + ? ? +|+ - - + -  80-89
+
  - + - ? +|+ - - + -  80-89
 
  - + +|+ - + - - + +  90-99
 
  - + +|+ - + - - + +  90-99
 
  -|
 
  -|
  
The 41-50 block then forces f(41)=-1, hence f(82)=+1:
+
The 41-50 block then forces f(41)=-1, hence f(82)=+1: '''GAH - sign error here'''
  
 
  0 1 2 3 4 5 6 7 8 9
 
  0 1 2 3 4 5 6 7 8 9
Line 259: Line 269:
 
  + ? -|- + + - + - -  60-69
 
  + ? -|- + + - + - -  60-69
 
  +|? + ? + - -|- +|?  70-79
 
  +|? + ? + - -|- +|?  70-79
  - + + ? +|+ - - + -  80-89
+
  - + - ? +|+ - - + -  80-89
 
  - + + + - + - - + +  90-99
 
  - + + + - + - - + +  90-99
 
  -|
 
  -|

Revision as of 09:29, 29 January 2010

It is known from computer search that the longest completely multiplicative sequence [math]f: [N] \to \{-1,+1\}[/math] of discrepancy 2 has length 246. Here we record the attempts to prove this by hand. Notation: we display our function in rows of 10, starting with 0. We use the notation that + and - denote values which are known to equal +1 or -1 respectively, and ? for unknown values. Thus, initially our array looks like this:

0 1 2 3 4 5 6 7 8 9

0|+ ? ? + ? ? ? ? +   0-9
? ? ? ? ? ? + ? ? ?   10-19
? ? ? ? ? + ? ? ? ?   20-29
? ? ? ? ? ? + ? ? ?   30-39

since f(n^2) = 1 for all square numbers.

The notions of a cut and a block will be useful. A cut occurs between n and n+1 whenever it can be proved that f[1,n] sums to 0; these can only occur when n is even. We indicate a cut by a bar | between n and n+1. Thus for instance we begin with just one cut:

0 1 2 3 4 5 6 7 8 9

0|+ ? ? + ? ? ? ? +   0-9
? ? ? ? ? ? + ? ? ?   10-19
? ? ? ? ? + ? ? ? ?   20-29
? ? ? ? ? ? + ? ? ?   30-39

A block is any interval between two cuts; thus inside each block one must sum to zero, and the discrepancy inside each block is at most 2. Thus we can "localise" the analysis to each block, though multiplicativity relates the blocks together.

A block is solved if all values are assigned in it. Solved blocks are uninteresting (other than for the values they provide by multiplicativity), so we shall adopt the convention of concatenating solved blocks with adjacent blocks to reduce clutter.

More notation: we use f[a,b] as short for f(a)+...+f(b). Note that

f[a,b] = -4,-2,0,2,4 if a is odd and b is even;
f[a,b] = -3,-1,1,3 if a and b are both odd or both even;
f[a,b] = -2,0,2 if a is even and b is odd.

Also if [a,b] starts or ends at a cut, then f[a,b] has magnitude at most 2.

A key observation is that if f(2n)=f(2n+1) then there must be a cut between 2n and 2n+1.

Case 1. f(2)=1

Now, let us assume f(2)=1 and that the discrepancy is at most 2 and see what happens. From multiplicativity we obtain f(2n^2)=1, thus

0 1 2 3 4 5 6 7 8 9

0|+ + ? + ? ? ? + +   0-9
? ? ? ? ? ? + ? + ?   10-19
? ? ? ? ? + ? ? ? ?   20-29
? ? + ? ? ? + ? ? ?   30-39

As f(8)=f(9) we can now cut at 8=9. And then by using discrepancy we get f(3)=f(5)=-1, thus

0 1 2 3 4 5 6 7 8 9

0|+ + - + - ? ? +|+   0-9
? ? ? ? ? ? + ? + ?   10-19
? ? ? ? ? + ? ? ? ?   20-29
? ? + ? ? ? + ? ? ?   30-39

which then by multiplicativity and adding cuts where obvious extends to

0 1 2 3 4 5 6 7 8 9

0 + + - + - -|? +|+   0-9
-|? - ? ? + + ? + ?   10-19
- ? ? ? - + ? - ? ?   20-29
+ ? + ? ? ? + ? ? ?   30-39

Looking at the 7-8 block we see that f(7) is forced to be -1; from this and multiplicativity, and showing rows up to 100, we arrive at

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
-|? - ? - + + ? + ?   10-19
- + ? ? - + ? - - ?   20-29
+ ? + ? ? + + ? ? ?   30-39
- ? + ? ? - ? ? - +   40-49
+ ? ? ? - ? - ? ? ?   50-59
+ ? ? ? + ? ? ? ? ?   60-69
+ ? + ? ? - ? ? ? ?   70-79
- + ? ? ? ? ? ? ? ?   80-89
- ? ? ? ? ? - ? + ?   90-99
-

Note that

f[15,19] = 3 + f(17) + f(19)

cannot exceed 3, and

f[168,171] = 2 - f(17) + f(19)

cannot exceed 2. Thus f(19) = -1. We use this information to update the board:

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
-|? - ? - + + ? + -   10-19
- + ? ? - + ? - - ?   20-29
+ ? + ? ? + + ? - ?   30-39
- ? + ? ? - ? ? - +   40-49
+ ? ? ? - ? - + ? ?   50-59
+ ? ? ? + ? ? ? ? ?   60-69
+ ? + ? ? - - ? ? ?   70-79
- + ? ? ? ? ? ? ? ?   80-89
- ? ? ? ? + - ? + ?   90-99
-

Let's write f(11)=a, f(13)=b, f(17)=c, f(23)=e, f(29)=f and A = -a, B = -b, C = -c, E=-e, F=-f. Then we can fill in more:

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
-|a - b - + + c + -   10-19
- + a e - + b - - f   20-29
+ ? + A c + + ? - B   30-39
- ? + ? a - e ? - +   40-49
+ C b ? - A - + f ?   50-59
+ ? ? - + B A ? c E   60-69
+ ? + ? ? - - A B ?   70-79
- + ? ? + C ? F a ?   80-89
- B C ? ? + - ? + a   90-99
-

This seems to be about as far as one can get just from the assumption f(2)=+1.

Case 1.a f(2)=f(37)=1

The most profitable assumption here seems to be f(37)=+1. This creates a cut at 36-37, which then forces f(34)=-1 and then f(33)=-1 also. Filling in these values and adding in cuts gives

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
- + -|b - + + - + -   10-19
- + + e - + b - - f   20-29
+ ? +|- - + +|+ - B   30-39
- ? + ? + - e ? - +   40-49
+ + b ? -|- - + f ?   50-59
+ ? ? - + B - ? - E   60-69
+ ? + ? + - -|- B ?   70-79
- + ? ? +|+ ? F + ?   80-89
- B + ? ? + - ? + +   90-99
-

looking at f[30,32] we thus have f(31)=-1,

0 1 2 3 4 5 6 7 8 9

0 + + - + - - - + +   0-9
- + -|b - + + - + -   10-19
- + + e - + b - - f   20-29
+|- + - - + +|+ - B   30-39
- ? + ? + - e ? - +   40-49
+ + b ? -|- - + f ?   50-59
+ ? - - + B - ? - E   60-69
+ ? + ? + - -|- B ?   70-79
- + ? ? +|+ ? F + ?   80-89
- B +|+ ? + - ? + +   90-99
-

Case 1.a.1 f(2)=f(37)=f(13)=1

Now suppose we assume b=+1. Then by looking at f(1)+...+f(23) we have e=-1, and by looking at f(1)+...+f(37) we then have f=-1, leaving us with

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - + - + + - + -   10-19
- + + - - + + - - -   20-29
+ - + - - + + + -|-   30-39
- ? + ? + - - ? - +   40-49
+|+ + ? -|- - + - ?   50-59
+ ? - - + - - ? - +   60-69
+ ? + ? + - -|- - ?   70-79
- + ? ? +|+ ? + + ?   80-89
-|- +|+ ? + - ? + +   90-99
-

from f[39,41] we have f(41)=+1, and from f[77,79] we have f(79)=+1, from f[51,54] we have f(53)=-1, from f[47,50] we have f(47)=-1, and from f[85,88] we have f(86)=-1, hence f(43)=-1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - + - + + - + -   10-19
- + + - - + + - - -   20-29
+ - + - - + + + - -   30-39
- + + - +|- - - - +   40-49
+ +|+ - - - - + - ?   50-59
+ ? - - + - - ? - +   60-69
+ ? + ? + - -|- - +   70-79
- + +|? + + - + + ?   80-89
- - + + ? + - ? + +   90-99
-

But this creates a contradiction at the block [45,51]. Thus this case is impossible.

Case 1.a f(2)=f(37)=1

We have thus concluded in this case that f(13)=-1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + +|e - + -|- - f   20-29
+|- + - - + +|+ - +   30-39
-|? + ? + - e ? - +   40-49
+|+ - ? -|- - + f ?   50-59
+ ? -|- + + -|? - E   60-69
+ ? + ? + - -|- + ?   70-79
- + ? ? +|+ ? F + ?   80-89
- + +|+ ? + - ? + +   90-99
-

From the [23,26] and [27,30] blocks we have e=+1 and f=+1; from the block [51,54] we have f(53)=+1. Looking at [93,95] we see that f(94)=-1 hence f(47)=+1, and we have a cut at 92-93, hence also at 96-97:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
-|? + ? +|- + - - +   40-49
+ + - + - - - + +|?   50-59
+ ? -|- + + -|? - -   60-69
+ ? + ? + - -|- +|?   70-79
- + ? ? +|+ ? - + ?   80-89
- + +|+ - + -|? + +   90-99
-

from f[97,99] we have f(97)=-1. From the [41,44] block we have f(41)=f(43)=-1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|?   50-59
+ ? -|- + + -|? -|-   60-69
+ ? + ? + - -|- +|?   70-79
- + - ? +|+ - - +|?   80-89
- + +|+ - + - - + +   90-99
-|

Using the cuts we can fill in f(67)=+1 and f(89)=-1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+|+ - ? - - - + + ?   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- +|?   70-79
- + - ? +|+ - - + -   80-89
- + +|+ - + - - + +   90-99
-|

The 41-50 block then forces f(41)=-1, hence f(82)=+1: GAH - sign error here

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + -|? - - - + + ?   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- +|?   70-79
- + - ? +|+ - - + -   80-89
- + + + - + - - + +   90-99
-|

The 79-84 block then forces f(79)=f(83)=-1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + -|? - - - + + ?   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|

Looking at 53-56 we see that f(53)=+1:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|?   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|

Suppose f(59)=+1. Then f(118)=f(120)=f(121)=1 and f(119)=-f(17), so f(17)=+1. Also, f(57)=f(59)=f(60)=1 and f(58)=f(29), hence f(29)=-1. Next, f(15)+…+f(22) = f(11)+2, hence f(11)=-1; and then f(1)+…+f(13) = f(13)-2, so f(13)=+1. But then f(1)+…+f(23)=f(23)+2, so f(23)=-1. But then f(1)+…+f(29)=-3, contradiction.

Thus we must also have f(59)=-1, so f(61)=+1.

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ + -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|

The remaining three question marks are unconstrained other than requiring every block to sum to 0. Now consider the sequence up to 119, with the multiplicative values filled in:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ + -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? - - + ? - ?   100-109
- - - ? + - + - - +   110-119

109 is clearly + (otherwise there’s a sequence of 5 -s).

Consider 101 and 103.

Both can’t be + because the sum at 103 would reach 3.

Both can’t be – because then at 105 the sum would reach -3.

Therefore one has to be + and the other -, so the sum is 0 immediately before 105 and 0 immediately before 107.

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ + -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|? - +   100-109
- - - ? + - + - - +   110-119

Since the sum is 0 before 107, 107 must be + (otherwise the sum is -3 at 111).

Also, the sum is -2 before 103, so 103 is +.

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ + -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|+ - +   100-109
- - - + +|- +|- - +   110-119

Continuing with known multiplicative values and values set by the sum being 2 or -2 up to 149:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|+ - +   100-109
- - - + +|- +|- - +   110-119
+ + + - - - - + + +   120-129
+ - - + + - -|? - ?   130-139
+ + ? - + - ? - + ?   140-149

107 and 109 can't both be + (sum reaches 3 at 141) and can't both be - (5 -s in a row) so before 141 the sum must be 0:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|+ - +   100-109
- - - + +|- +|- - +   110-119
+ + + - - - - + + +   120-129
+ - - + + - -|? - ?   130-139
+|+ ? - + - ? - + ?   140-149

Extending through multiplicative knowledge ...

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|+ - +   100-109
- - - + +|- +|- - +   110-119
+ + + - - - - + + +   120-129
+ - - + + - -|? - ?   130-139
+|+ ? - + - ? - + ?   140-149
- ? - - - + + ? - -   150-159

We know 71 and 73 must be alternate signs, so by multiplicative properties 142 (2 * 71) and 146 2 * 73) must have alternate signs, so the sum is zero immediately before 147 and 149. Now extending the list to 159:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|+ - +   100-109
- - - + +|- +|- - +   110-119
+ + + - - - - + + +   120-129
+ - - + + - -|? - ?   130-139
+|+ ? - + - ?|- +|?   140-149
- ? - - - + + ? - -   150-159

151 must be + because otherwise we have 5 -s in a row, and 149 must be + because otherwise the sum will be -3 at 153, so immediately before 157 the sum is 0:

0 1 2 3 4 5 6 7 8 9
0 + + - + - - - + +   0-9
- + - - - + + - + -   10-19
- + + + - + - - - +   20-29
+ - + - - + + + - +   30-39
- - + - + - + - - +   40-49
+ + - + - - - + +|-   50-59
+ ? -|- + + - + - -   60-69
+|? + ? + - -|- + -   70-79
- + + - + + - - + -   80-89
- + + + - + - - + +   90-99
-|? + ? -|- +|+ - +   100-109
- - - + +|- +|- - +   110-119
+ + + - - - - + + +   120-129
+ - - + + - -|? - ?   130-139
+|+ ? - + - ?|- +|+   140-149
- + - - - + +|? - -   150-159