Polymath Wiki - User contributions [en]

Imo 2010

2010-07-26T12:04:33Z

Mark Bennet: /* Compound moves */ typo

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \to [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \to [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \to [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \to [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a]</math>.
# For <math>a \geq 1</math> we have <math>[a,0,0] \to [0,2^a,0]</math> via <math>[a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0]</math>.
#* Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
# For <math>a,b \geq 1</math> we have <math>[a,b,0,0] \to [a-1, 2^b, 0, 0]</math>. This follows from the previous compound move together with a Type 2 swap.
# For <math>a \geq 2</math> we have <math>[a,b,0,0] \to [a-2, 2^{b+2}, 0, 0]</math>, which is valid for <math>b=0</math> as well. This follows from applying a Type 1 move to <math>[a,b]</math> and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

#a <math>[n,0] \to [0,2n]</math>
#a <math>[n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ]</math>
#* because <math>[n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0]</math> by repeated applications of 1a
#a <math> [n,0,0,0] \to </math>[0,2^^n,0,0] <math> \to </math> [0,0,2^(2^^n),0]<math> \to </math> [0,0,0,2*2^(2^^n)]
#* because <math>[n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0]</math> by repeated applications of 2a, giving [0,2^^n,0,0]
#a similarly <math> [n,0,0,0,0] \to </math>[0,2^^^n,0,0,0] etc

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

<math>[1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0]</math><math> \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}]</math> with a record of <math>2*2^{2^{14}}</math>

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, do 2 to power [result], do 2 to power [result], multiply by 2.

The first item on the second row has <math>2^{14}</math> as far left as possible and is used ...

To make the sixth box as big as possible

* Using the move we identified we get to <math> \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0]</math>

Sorry can't see how to do a double Knuth uparrow

* Then we get <math> \to </math> [0,1,0,2^^(2^(14)),0,0]<math> \to </math> [0,0,2^^(2^(14)),0,0,0]<math> \to </math> [0,0,0,2^^(2^^(2^(14))),0,0]
<math> \to </math>[0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))]
The structure Take 7, multiply by two, do 2 to power [result], do 2 double up-arrow [result], do 2 double up-arrow [result], do 2 to power [result], multiply by 2.

TO MAKE THE FINAL BOX AS SMALL AS POSSIBLE WITH ALL OTHERS ZERO

I reckon the answer is:

[1] - last box is 1

[1,1] last box is 3 (only move)

[1,1,1] last box is 3 (do type 2 with first box)

[1,1,1,1] to [1,1,0,3] to [1,0,3,0] to [0,3,0,0] to [0,0,0,0] (type 2 moves exchanging zeros) last box is zero

[1,1,1,1,1] do type 2 with first box (exchanging 1s) to [0,1,1,1,1] then as before [0,0,0,0,0] ... etc

== Completed solutions ==

=== First solution ===
Let <math>T = 2010^{2010^{2010}}</math>.

We will be done if we can obtain the configuration <math>[0,0,0,T/4,0,0]</math>, for then we can apply two compound move 1s to get the <math>[0,0,0,0,0,T]</math>.

To get this configuration it is enough to get a configuration <math>[0,0,0,X,0,0]</math> for some <math>X \geq T/4</math>, because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to <math>T/4</math>.

Finally, one can obtain such a configuration using compound move 4. First note that we can get <math>[0,0, 140, 0, 0 ,0]</math>:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

From this we get <math>[0,0, 139, 2, 0 ,0]</math>, and then by applying compound move 4 139 times we get <math>[0,0, 0, X, 0 ,0]</math> for some <math>X</math> much, much bigger than <math>T/4</math>, and so we are done.

=== Second solution ===

Imo 2010

2010-07-20T20:06:10Z

Mark Bennet: /* World records */ Correcting inaccurate statement and clarifying formulae

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \to [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \to [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \to [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \to [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a]</math>.
# For <math>a \geq 1</math> we have <math>[a,0,0] \to [0,2^a,0]</math> via <math>[a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0]</math>.
#* Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
# For <math>a,b \geq 1</math> we have <math>[a,b,0,0] \to [a-1, 2^b, 0, 0]</math>. This follows from the previous compound move together with a Type 2 swap.
# For <math>a \geq 2</math> we have <math>[a,b,0,0] \to [a-2, 2^{b+2}, 0, 0]</math>, which is valid for <math>b=0</math> as well. This follows from applying a Type 1 move to <math>[a,b]</math> and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

#a <math>[n,0] \to [0,2n]</math>
#a <math>[n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ]</math>
#* because <math>[n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0]</math> by repeated applications of 1a
#a <math> [n,0,0,0] \to </math>[0,2^^n,0] <math> \to </math> [0,0,2^(2^^n),0]<math> \to </math> [0,0,0,2*2^(2^^n)]
#* because <math>[n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0]</math> by repeated applications of 2a, giving [0,2^^n,0,0]
#a similarly <math> [n,0,0,0,0] \to </math>[0,2^^^n,0,0,0] etc

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

<math>[1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0]</math><math> \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}]</math> with a record of <math>2*2^{2^{14}}</math>

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, do 2 to power [result], do 2 to power [result], multiply by 2.

The first item on the second row has <math>2^{14}</math> as far left as possible and is used ...

To make the sixth box as big as possible

* Using the move we identified we get to <math> \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0]</math>

Sorry can't see how to do a double Knuth uparrow

* Then we get <math> \to </math> [0,1,0,2^^(2^(14)),0,0]<math> \to </math> [0,0,2^^(2^(14)),0,0,0]<math> \to </math> [0,0,0,2^^(2^^(2^(14))),0,0]
<math> \to </math>[0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))]
The structure Take 7, multiply by two, do 2 to power [result], do 2 double up-arrow [result], do 2 double up-arrow [result], do 2 to power [result], multiply by 2.

TO MAKE THE FINAL BOX AS SMALL AS POSSIBLE WITH ALL OTHERS ZERO

I reckon the answer is:

[1] - last box is 1

[1,1] last box is 3 (only move)

[1,1,1] last box is 3 (do type 2 with first box)

[1,1,1,1] to [1,1,0,3] to [1,0,3,0] to [0,3,0,0] to [0,0,0,0] (type 2 moves exchanging zeros) last box is zero

[1,1,1,1,1] do type 2 with first box (exchanging 1s) to [0,1,1,1,1] then as before [0,0,0,0,0] ... etc

== Completed solutions ==

=== First solution ===
Let <math>T = 2010^{2010^{2010}}</math>.

We will be done if we can obtain the configuration <math>[0,0,0,T/4,0,0]</math>, for then we can apply two compound move 1s to get the <math>[0,0,0,0,0,T]</math>.

To get this configuration it is enough to get a configuration <math>[0,0,0,X,0,0]</math> for some <math>X \geq T/4</math>, because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to <math>T/4</math>.

Finally, one can obtain such a configuration using compound move 4. First note that we can get <math>[0,0, 140, 0, 0 ,0]</math>:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

From this we get <math>[0,0, 139, 2, 0 ,0]</math>, and then by applying compound move 4 139 times we get <math>[0,0, 0, X, 0 ,0]</math> for some <math>X</math> much, much bigger than <math>T/4</math>, and so we are done.

=== Second solution ===

Imo 2010

2010-07-16T21:48:51Z

Mark Bennet: /* World records */ lowest scores

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \to [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \to [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \to [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \to [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a]</math>.
# For <math>a \geq 1</math> we have <math>[a,0,0] \to [0,2^a,0]</math> via <math>[a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0]</math>.
#* Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
# For <math>a,b \geq 1</math> we have <math>[a,b,0,0] \to [a-1, 2^b, 0, 0]</math>. This follows from the previous compound move together with a Type 2 swap.
# For <math>a \geq 2</math> we have <math>[a,b,0,0] \to [a-2, 2^{b+2}, 0, 0]</math>, which is valid for <math>b=0</math> as well. This follows from applying a Type 1 move to <math>[a,b]</math> and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

#a <math>[n,0] \to [0,2n]</math>
#a <math>[n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ]</math>
#* because <math>[n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0]</math> by repeated applications of 1a
#a <math> [n,0,0,0] \to </math>[0,2^^n,0] <math> \to </math> [0,0,2^(2^^n),0]<math> \to </math> [0,0,0,2*2^(2^^n)]
#* because <math>[n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0]</math> by repeated applications of 2a, giving [0,2^^n,0,0]
#a similarly <math> [n,0,0,0,0] \to </math>[0,2^^^n,0,0,0] etc

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

<math>[1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0]</math><math> \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}]</math> with a record of <math>2*2^{2^{14}}</math>

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, raise to the power 2, raise to the power 2, multiply by 2.

The first item on the second row has <math>2^{14}</math> as far left as possible and is used ...

To make the sixth box as big as possible

* Using the move we identified we get to <math> \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0]</math>

Sorry can't see how to do a double Knuth uparrow

* Then we get <math> \to </math> [0,1,0,2^^(2^(14)),0,0]<math> \to </math> [0,0,2^^(2^(14)),0,0,0]<math> \to </math> [0,0,0,2^^(2^^(2^(14))),0,0]
<math> \to </math>[0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))]
The structure Take 7, multiply by two, raise to power 2, do 2 double up-arrow, do 2 double up-arrow, raise to power 2, multiply by 2.

TO MAKE THE FINAL BOX AS SMALL AS POSSIBLE WITH ALL OTHERS ZERO

I reckon the answer is:

[1] - last box is 1

[1,1] last box is 3 (only move)

[1,1,1] last box is 3 (do type 2 with first box)

[1,1,1,1] to [1,1,0,3] to [1,0,3,0] to [0,3,0,0] to [0,0,0,0] (type 2 moves exchanging zeros) last box is zero

[1,1,1,1,1] do type 2 with first box (exchanging 1s) to [0,1,1,1,1] then as before [0,0,0,0,0] ... etc

== Completed solutions ==

=== First solution ===
Let <math>T = 2010^{2010^{2010}}</math>.

We will be done if we can obtain the configuration <math>[0,0,0,T/4,0,0]</math>, for then we can apply two compound move 1s to get the <math>[0,0,0,0,0,T]</math>.

To get this configuration it is enough to get a configuration <math>[0,0,0,X,0,0]</math> for some <math>X \geq T/4</math>, because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to <math>T/4</math>.

Finally, one can obtain such a configuration using compound move 4. First note that we can get <math>[0,0, 140, 0, 0 ,0]</math>:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

From this we get <math>[0,0, 139, 2, 0 ,0]</math>, and then by applying compound move 4 139 times we get <math>[0,0, 0, X, 0 ,0]</math> for some <math>X</math> much, much bigger than <math>T/4</math>, and so we are done.

=== Second solution ===

Imo 2010

2010-07-12T22:04:34Z

Mark Bennet:

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \to [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \to [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \to [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \to [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a]</math>.
# For <math>a \geq 1</math> we have <math>[a,0,0] \to [0,2^a,0]</math> via <math>[a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0]</math>.
#* Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
# For <math>a,b \geq 1</math> we have <math>[a,b,0,0] \to [a-1, 2^b, 0, 0]</math>. This follows from the previous compound move together with a Type 2 swap.
# For <math>a \geq 2</math> we have <math>[a,b,0,0] \to [a-2, 2^{b+2}, 0, 0]</math>, which is valid for <math>b=0</math> as well. This follows from applying a Type 1 move to <math>[a,b]</math> and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

#a <math>[n,0] \to [0,2n]</math>
#a <math>[n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ]</math>
#* because <math>[n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0]</math> by repeated applications of 1a
#a <math> [n,0,0,0] \to </math>[0,2^^n,0] <math> \to </math> [0,0,2^(2^^n),0]<math> \to </math> [0,0,0,2*2^(2^^n)]
#* because <math>[n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0]</math> by repeated applications of 2a, giving [0,2^^n,0,0]
#a similarly <math> [n,0,0,0,0] \to </math>[0,2^^^n,0,0,0] etc

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

<math>[1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0]</math><math> \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}]</math> with a record of <math>2*2^{2^{14}}</math>

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, raise to the power 2, raise to the power 2, multiply by 2.

The first item on the second row has <math>2^{14}</math> as far left as possible and is used ...

To make the sixth box as big as possible

* Using the move we identified we get to <math> \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0]</math>

Sorry can't see how to do a double Knuth uparrow

* Then we get <math> \to </math> [0,1,0,2^^(2^(14)),0,0]<math> \to </math> [0,0,2^^(2^(14)),0,0,0]<math> \to </math> [0,0,0,2^^(2^^(2^(14))),0,0]
<math> \to </math>[0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))]
The structure Take 7, multiply by two, raise to power 2, do 2 double up-arrow, do 2 double up-arrow, raise to power 2, multiply by 2.

== Completed solutions ==

=== First solution ===
Let <math>T = 2010^{2010^{2010}}</math>.

We will be done if we can obtain the configuration <math>[0,0,0,T/4,0,0]</math>, for then we can apply two compound move 1s to get the <math>[0,0,0,0,0,T]</math>.

To get this configuration it is enough to get a configuration <math>[0,0,0,X,0,0]</math> for some <math>X \geq T/4</math>, because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to <math>T/4</math>.

Finally, one can obtain such a configuration using compound move 4. First note that we can get <math>[0,0, 140, 0, 0 ,0]</math>:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

From this we get <math>[0,0, 139, 2, 0 ,0]</math>, and then by applying compound move 4 139 times we get <math>[0,0, 0, X, 0 ,0]</math> for some <math>X</math> much, much bigger than <math>T/4</math>, and so we are done.

=== Second solution ===

Imo 2010

2010-07-12T22:03:49Z

Mark Bennet: typo

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \to [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \to [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \to [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \to [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a]</math>.
# For <math>a \geq 1</math> we have <math>[a,0,0] \to [0,2^a,0]</math> via <math>[a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0]</math>.
#* Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
# For <math>a,b \geq 1</math> we have <math>[a,b,0,0] \to [a-1, 2^b, 0, 0]</math>. This follows from the previous compound move together with a Type 2 swap.
# For <math>a \geq 2</math> we have <math>[a,b,0,0] \to [a-2, 2^{b+2}, 0, 0]</math>, which is valid for <math>b=0</math> as well. This follows from applying a Type 1 move to <math>[a,b]</math> and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

#a <math>[n,0] \to [0,2n]</math>
#a <math>[n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ]</math>
#* because <math>[n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0]</math> by repeated applications of 1a
#a <math> [n,0,0,0] \to </math>[0,2^^n,0] <math> \to </math> [0,0,2^(2^^n),0]<math> \to </math> [0,0,0,2*2^(2^^n)]
#* because <math>[n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0]</math> by repeated applications of 2a, giving [0,2^^n,0,0]
#a similarly <math> [n,0,0,0,0] \to </math>[0,2^^^n,0,0,0] etc

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

<math>[1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0]</math><math> \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}]</math> with a record of <math>2*2^{2^{14}}</math>

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, raise to the power 2, raise to the power 2, multiply by 2.

The first item on the second row has <math>2^{14}</math> as far left as possible and is used ...

To make the sixth box as big as possible

* Using the move we identified we get to <math> \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0]</math>

Sorry can't see how to do a double Knuth uparrow

* Then we get <math> \to </math> [0,1,0,2^^(2^(14)),0,0]<math> \to </math> [0,0,2^^(2^(14)),0,0,0]<math> \to </math> [0,0,0,2^^(2^^(2^(14))),0,0]
<math> \to </math>[0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))]
The structure Take 7, multiply by two, raise to power 2, do 2 double up-arrow, do 2 double up-arrow, raise to power 2, multiply by 2.

== Completed solutions ==

=== First solution ===
Let <math>T = 2010^{2010^{2010}}</math>.

We will be done if we can obtain the configuration <math>[0,0,0,T/4,0,0]</math>, for then we can apply two compound move 1s to get the <math>[0,0,0,0,0,T]</math>.

To get this configuration it is enough to get a configuration <math>[0,0,0,X,0,0]</math> for some <math>X \geq T/4</math>, because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to <math>T/4</math>.

Finally, one can obtain such a configuration using compound move 4. First note that we can get <math>[0,0, 140, 0, 0 ,0]</math>:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

From this we get <math>[0,0, 139, 2, 0 ,0]</math>, and then by applying compound move 4 139 times we get <math>[0,0, 0, X, 0 ,0]</math> for some <math>X</math> much, much bigger than <math>T/4</math>, and so we are done.

=== Second solution ===

Imo 2010

2010-07-12T21:34:35Z

Mark Bennet: Adding some observations on patterns and records

This is the wiki page for the mini-polymath2 project, which seeks solutions to Question 5 of the 2010 International Mathematical Olympiad.

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2010&month=7&day=8&hour=16&min=0&sec=0&p1=0 16:00 UTC July 8], and is hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread is hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should probably refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others.

== Threads ==

Discussion and planning:

* [http://terrytao.wordpress.com/2010/06/12/future-mini-polymath-project-2010-imo-q6/ Future mini-polymath project: 2010 IMO Q6?] June 12, 2010.
* [http://terrytao.wordpress.com/2010/06/21/organising-mini-polymath2/ Organising mini-polymath2] June 21, 2010.
* [http://terrytao.wordpress.com/2010/06/27/mini-polymath2-start-time/ Mini-polymath2 start time], June 27, 2010.
* [http://terrytao.wordpress.com/2010/07/08/mini-polymath2-discussion-thread/ Mini-polymath2 discussion thread], July 8 2010.

Research:

* [http://polymathprojects.org/2010/07/08/minipolymath2-project-imo-2010-q5/ Minipolymath2 project: IMO 2010 Q5], July 8 2010.

== The question ==

The question to be solved is Question 5 of the [http://www.imo-official.org/problems.aspx 2010 International Mathematical Olympiad]:

: '''Problem''' In each of six boxes <math>B_1, B_2, B_3, B_4, B_5, B_6</math> there is initially one coin. There are two types of operation allowed:
:
: ''Type 1:'' Choose a nonempty box <math>B_j</math> with <math>1 \leq j \leq 5</math>. Remove one coin from <math>B_j</math> and add two coins to <math>B_{j+1}</math>.
:
: ''Type 2:'' Choose a nonempty box <math>B_k</math> with <math>1 \leq k \leq 4</math>. Remove one coin from <math>B_k</math> and exchange the contents of (possibly empty) boxes <math>B_{k+1}</math> and <math>B_{k+2}</math>.
:
: Determine whether there is a finite sequence of such operations that results in boxes <math>B_1, B_2, B_3, B_4, B_5</math> being empty and box <math>B_6</math> containing exactly <math>2010^{2010^{2010}}</math> coins. (Note that <math>a^{b^c} := a^{(b^c)}</math>.)

== Observations and partial results ==

* If the left-most box <math>B_1</math> becomes empty, then it cannot ever become non-empty again. Furthermore, the left-most box can never have more than one coin; it can be touched exactly once.
* Define the ''worth'' W of a state to be <math>W = B_6 + 2 B_5 + 4 B_4 + 8 B_3 + 16 B_2 + 32 B_1</math>. Then the initial worth is 63, the final desired worth is <math>2010^{2010^{2010}}</math>, and the Type 1 move does not affect the worth. On the other hand, the Type 2 move increases the worth when <math>B_{j+2} - B_{j+1} \geq 4</math>.
* Once one has a large number of coins in one of the first four boxes, say <math>B_k</math>, one can apply the Type 2 move repeatedly to remove coins from <math>B_k</math> while swapping <math>B_{k+1}</math> and <math>B_{k+2}</math> repeatedly. This suggests that it is relatively easy to remove coins from the system; the difficulty is in adding coins to the system.
* The total number of coins in the system is bounded. Indeed, let <math>f(N,\Sigma)</math> be the maximum number of coins that one can end up with starting with N boxes with at most <math>\Sigma</math> coins in them. Thus for instance <math>f(1,\Sigma)=\Sigma</math>. By considering the times when one touches the left-most box, we can bound <math>f(N,\Sigma)</math> by at most <math>\Sigma</math> iterations of the map <math>n \mapsto f(N-1,n)+2</math> starting with <math>n=\Sigma</math>. This gives an Ackermann-type bound on <math>f(N,\Sigma)</math>. We need f(6,6) to be less than <math>2010^{2010^{2010}}</math>, but this bound is likely to be too large.

== Possible strategies ==

* Split the problem into two pieces. Part I: try to show the weaker result that the number of coins in the system can eventually be as large as <math>2010^{2010^{2010}}</math>. Part II: Show that once one has a lot of coins, one can move to the final state where <math>B_1=\ldots=B_5=0</math> and <math>B_6 = 2010^{2010^{2010}}</math>.
* Try to show that a quantity such as the worth increases or decreases in a controlled manner as one applies the Type 1 and Type 2 moves.
* We know that the first box can never contain more than one coin. What can we say about the second box, third box, etc.?
** There may be a recursive formula for the maximal size of box <math>B_j</math>, possibly requiring one to solve the five-box, four-box, etc. problems first.
* Work backwards?
* Try to completely solve the three-box problem (say) first: starting from <math>[X,Y,Z]</math>, what is the most number of coins one can generate?

== Compound moves ==

Here we use Type 1 move <math>[a,b] \to [a-1,b+2]</math> and the Type 2 move <math>[a,b,c] \to [a-1,c,b]</math> to create more advanced moves.

# We can create the move <math>[a,b] \to [0,b+2a]</math> from repeated application of Type 1.
# We have <math>[1,a,b] \to [0,0,a+2b]</math> by applying Type 2 once and then Type 1 b times.
#* Or, by using advanced move 1 first, the move <math>[1, a, b] \to [1, 0, b+2a] \to [0, b+2a, 0] \to [0, 0, 2b+4a]</math>.
# For <math>a \geq 1</math> we have <math>[a,0,0] \to [0,2^a,0]</math> via <math>[a,0,0] \to [a-1,2,0] \to [a-1,0,4] \to [a-2,4,0] \to [a-2,0,8] \to \ldots \to [1, 0, 2^a] \to [0,2^a,0]</math>.
#* Note that, except for the first move, the coins in the left-most box here are only being used for Type 2 swaps, and otherwise compound move 1 is being applied to the second two boxes.
# For <math>a,b \geq 1</math> we have <math>[a,b,0,0] \to [a-1, 2^b, 0, 0]</math>. This follows from the previous compound move together with a Type 2 swap.
# For <math>a \geq 2</math> we have <math>[a,b,0,0] \to [a-2, 2^{b+2}, 0, 0]</math>, which is valid for <math>b=0</math> as well. This follows from applying a Type 1 move to <math>[a,b]</math> and then applying the previous compound move.

The last two moves seems to be the key to the solutions so far discovered, since it allows one to introduce an exponential at only a linear cost.

Note that we have (and if someone can fix the arrows here and below that would be good)

#a <math>[n,0] \to [0,2n]</math>
#a <math>[n,0,0] \to [0,2^n,0] \to [0,0,2*2^n ]</math>
#* because <math>[n,0,0] \to [n-1,2,0] \to [n-1,0,4] \to [n-2,4,0]</math> by repeated applications of 1a
#a <math> [n,0,0,0] \to </math>[0,2^^n,0] <math> \to </math> [0,0,2^(2^^n),0]<math> \to </math> [0,0,0,2*2^(2^^n)]
#* because <math>[n,0,0,0] \to [n-1,2,0,0] \to [n-1,0,2^2,0] \to [n-2,2^2,0,0]\to [n-2,0,2^{2^2},0] \to [n-3,2^{2^2},0,0]</math> by repeated applications of 2a, giving [0,2^^n,0,0]
#a similarly <math> [n,0,0,0,0] \to </math>[0,2^^^n,0,0,0 etc]

== World records ==

To make the second box as big as possible:

* <math>[1,1,1] \mapsto [1,0,3] \mapsto [0,3,0]</math> places 3 coins in box 2.

To make the third box as big as possible:

* <math>[1,1,1] \mapsto [0,3,1] \mapsto [0,0,7]</math> places 7 coins in box 3. (Here we use advanced move 2).

To make the fourth box as big as possible

* <math>[1,1,1,1] \to [0,3,0,3] \to [0,2,2,3] \to [0,2,0,7] \to [0,1,7,0] \to [0,1,0,14]</math> <math> \to [0,0,14,0] \to [0,0,0,28]</math> gives 28 coins in box 4.

Note that 28 is 2*(2*7), and that the penultimate step has the 14=2*7 as far left as possible.

To make the fifth box as big as possible

<math>[1,1,1,1,1] \to [1,0,0,14,0] \to [0,2,0,14,0] \to [0,1,14,0,0] \to [0,1,0,2^{14},0]</math><math> \to [0,0,2^{14},0,0] \to [0,0,0,2^{2^{14}},0] \to [0,0,0,0,2*2^{2^{14}}]</math> with a record of <math>2*2^{2^{14}}</math>

The structure is more evident if you write 14=2*7. The process is take 7, multiply by 2, raise to the power 2, raise to the power 2, multiply by 2.

The first item on the second row has <math>2^{14}</math> as far left as possible and is used ...

To make the sixth box as big as possible

* Using the move we identified we get to <math> \to [1,0,0,2^{14},0,0] \to [0,2,0,2^{14},0,0] \to [0,1,2^{14},0,0,0]</math>

Sorry can't see how to do a double Knuth uparrow

* Then we get <math> \to </math> [0,1,0,2^^(2^(14)),0,0]<math> \to </math> [0,0,2^^(2^(14)),0,0,0]<math> \to </math> [0,0,0,2^^(2^^(2^(14))),0,0]
<math> \to </math>[0,0,0,0,2^(2^^(2^^(2^(14)))),0] to [0,0,0,0,0,2*2^(2^^(2^^(2^(14))))]
The structure Take 7, multiply by two, raise to power 2, do 2 double up-arrow, do 2 double up-arrow, raise to power 2, multiply by 2.

== Completed solutions ==

=== First solution ===
Let <math>T = 2010^{2010^{2010}}</math>.

We will be done if we can obtain the configuration <math>[0,0,0,T/4,0,0]</math>, for then we can apply two compound move 1s to get the <math>[0,0,0,0,0,T]</math>.

To get this configuration it is enough to get a configuration <math>[0,0,0,X,0,0]</math> for some <math>X \geq T/4</math>, because we can then apply Type 2 moves until the number of coins in the fourth box is reduced to <math>T/4</math>.

Finally, one can obtain such a configuration using compound move 4. First note that we can get <math>[0,0, 140, 0, 0 ,0]</math>:

:<math>[1,1,1,1,1,1] \to [0,2,2,2,2,3] \to [0,2,1,1,8,3] \to [0,2,1,1,0,19] \to [0,1,19,0,0,0]</math>
:<math>\to [0,1,1,36,0,0] \to [0,1,1,1,0,140] \to [0,0,140,0,0,0]</math>

From this we get <math>[0,0, 139, 2, 0 ,0]</math>, and then by applying compound move 4 139 times we get <math>[0,0, 0, X, 0 ,0]</math> for some <math>X</math> much, much bigger than <math>T/4</math>, and so we are done.

=== Second solution ===

Human proof that completely multiplicative sequences have discrepancy greater than 2

2010-01-30T11:13:11Z

Mark Bennet: Heading

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|+ ? ? + ? ? ? ? + 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.

If 79 and 83 are both positive the sum at 85 is 3, and if 79 and 83 are both negative the sum at 82 is -3, so 79 and 83 must be alternate signs, so there is a cut before 85:

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 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, this gives deductions:
120 = +1, 121=+1, 122=+1, 123=+1 and together with 119=+1 this provides a contradiction based on earlier values at 2,3,5; 2,61; 3,41 and 7,17
This concludes case 1a.

== Case 1.b f(2)=1, f(37)=-1 ==

This takes us back to case 1.b f(2)=1, f(37)=-1, which begins here:

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.

So we assume f(37)=-1

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
-

Human proof that completely multiplicative sequences have discrepancy greater than 2

2010-01-30T11:09:09Z

Mark Bennet: Contradiction at value 123 ends case f(2)=f(37)=+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. 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.

If 79 and 83 are both positive the sum at 85 is 3, and if 79 and 83 are both negative the sum at 82 is -3, so 79 and 83 must be alternate signs, so there is a cut before 85:

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 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, this gives deductions:
120 = +1, 121=+1, 122=+1, 123=+1 and together with 119=+1 this provides a contradiction based on earlier values at 2,3,5; 2,61; 3,41 and 7,17

This takes us back to case 1.b f(2)=1, f(37)=-1, which begins here:

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.

So we assume f(37)=-1

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
-

Human proof that completely multiplicative sequences have discrepancy greater than 2

2010-01-30T10:44:02Z

Mark Bennet: Deduction of 141 - typo: 137 and 139 rather than 107 and 109

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|+ ? ? + ? ? ? ? + 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.

If 79 and 83 are both positive the sum at 85 is 3, and if 79 and 83 are both negative the sum at 82 is -3, so 79 and 83 must be alternate signs, so there is a cut before 85:

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 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

137 and 139 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

Sequence of length 1112

2010-01-12T07:48:15Z

Mark Bennet: Subsequence analysis

This sequence, of length 1112 (close to the current record) may be of interest because it was derived differently from the 1124 sequences, by a depth-first search starting with a sequence of length 974 satisfying 1=-2=-5 and 11=-13 exactly:

0+--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++--+--+-
++-++----++-++--+-++--+--+-+++-+--+-+--++--+-++-++--+-++--+-
-+-++--+-++-+++-+--+-++--+--+-++-++--+--+-++--+-++--++-+-+-+
+---+-++-++---+++--+--+-++-++--+--+--+-++-++--+--+-++-++--+-
++--+--+-++-++--++---++--+-+-+++--+-++--++---++-+--++-++--+-
-+-++--+-++-++--+-++--++-+--+-+--+++-+--+-++---++--++--+++-+
--+-+-+--+++-+-++----++-+++--+-+--+-++--+-++-++--+-++--+--++
+---+-+--++++---+--+-+++---++-++--+-++--+--+-++--+-++-++--+-
-+-++++---+-++--++-+-++--+--+-++-+--+++-+--+--+-++-++--++---
-+-++-++-++----++-++---++++-+----++--++++--+-++--+--+-++-++-
+---+--+-++-++--++-+--+--+-++-++-++--+--+-++---+++--+-++-++-
--+++--+---++--++-++--++-+-+--+-+-+--++++--+---+++-++--++---
+++---+--+++--+++--+---+++-++----++-+++-+--+--+--+-+-++++---
++--+-++--+--+-++-++-++--+-++--+--+-+--++--+-++-++--+-++--+-
-+++---++-+-++-+-+--++-+--+-+-++--+--+-++++---+-+--+++---+++
-+--+++---+--+-++++--+--++--++---++-++--+-++--++--+++--+--++
+--++--+---++++--++---++-+-++-+-+---++-+---+++-+--++--+++---
-++++--+--+-+-++-+-+--+++--+-++-+--+--+++---+-++---++-++--+-
+--++--+-+-+-++--++-++--+++-+---+

As expected the subsequence structure is very similar to that for the 974 sequence

617: 1 4 10 13 16 19 22 25 27 31 34 40 42 46 52 55 58 64 76 82 85

3478: 2 5 8 11 17 20 21 23 26 29 32 38 41 44 50 54 59 62 65 68 80 83

809: 18 37 45 72 79

3286; 9 36 74

873: 7 28 49 70

3222: 14 35 47 56 77

1458: 3 12 30 39 48 57 66 75

2637: 6 15 24 33 43 51 60 63 69 78

242: 67
845: 73
1266: 53
1430: 84
1833: 61
3314: 71
3506: 81

This reflects the beginning of the subsequences. There are some emerging methods for analysing over the whole length which may give insight into the way in which patterns break up.

T m(x) = (+/-)T n(x)

2010-01-11T19:14:01Z

Mark Bennet: Correcting oversight on 11-sequence

This sequence, of length 974, satisfies the following relations exactly:

<math>x_{2n} = -x_n</math>

<math>x_{5n} = -x_n</math>

<math>x_{13n} = -x_{11n}</math>

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++----++-++--+-++--+--+-+++
-+--+-+--++--+-++-++--+-++--+-
-+-++--+-++-+++-+--+-++--+--+-
++-++--+--+-++--+-++--++-+-+-+
+---+-++-++---+++--+--+-++-++-
-+--+--+-++-++--+--+-++-++--+-
++--+--+-++-++--++---++--+-+-+
++--+-++--++---++-+--++-++--+-
-+-++--+-++-++--+-++--++-+--+-
+--+++-+--+-++---++--++--+++-+
--+-+-+--+++-+-++----++-+++--+
-+--+-++--+-++-++--+-++--+--++
+---+-+--++++---+--+-+++---++-
++--+-++--+--+-++--+-++-++--+-
-+-++++---+-++--++-+-++--+--+-
++-+--+++-+--+--+-++-++--++---
-+-++-++-++----++-++---++++-+-
-+-++---+++--+-++--+--+-++-++-
+---+--+-++-++--++-+--+--+-++-
++-++--+--+++----+++--+-++--++
--+++--+-+--++-++-+---++-+--+-
+-++---++++--+--+++--+---++--+
+++---++-++---+++--+---+++-++-
-+-++-+-+-+--+--+--+-+-++++---
++--+-++--+--+-++-++-++--+-++-
-+-++-+---++-+-++-+---+-++---+
-++-+-++-++---+++--+-+-+--+-+-
++-++-+---++-+---++-+++----++-
-+-++++---++-+-++-+---+-++--++
-+-++-+---++-+--+--+-++-++--+-
++--++-+-+-+-++

<math>x_{11n} = -x_n</math> up to position 63 - and 63 emerges as a new anomaly.

617: 1 4 10 13 16 19 22 25 27 31 34 40 42 46 52 55 58 64

3478: 2 5 8 11 17 20 21 23 26 29 32 38 41 44 50 54 59 62 65 68

809: 18 37 45 61 72

3286: 9 36 74

873: 7 28 49 70

3222: 14 35 47 56

1458: 3 12 30 39 48 57 66

2637: 6 15 24 33 43 51 60 69 73

Sporadic

242: 67

1266: 53 71

3661: 63

49 appears to be in the wrong place, but the 49-sequence is equal to the 7-sequence as far as position 19.

Length 854:

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++----++-++--+-++--++-+-++-
-+--+-+--++--+-++-++--+-++--+-
-+-++--+-++-+++-+--+-++--+--+-
++-++--+--+-++---+++--++-+-++-
+---+-++-++---+++--+--+-++-++-
-+-++--+-++-+---++---++-++--+-
++--+--+-++-++--++---++--+-+-+
++--+-++--++-+-++-+---+-++--+-
-+-++--+-++-++--+-++--++-+--+-
+-++-+-+--+-++---+++-++--+-++-
--+-+-+--+++-+-++--+--+-+++---
-+-++-++--+-++-++--+-++----+++
+---+--+-++++---+--+-++--++-+-
++-+--+++-+--+-++----++-++--+-
-+-++++---+-++--++-+-++--+--+-
++-+--+++-+--+--+-++-++--++---
-+-++-++-++----++-++---+++--++
-+-++---+-+-++-++--+--+-++--++
+--++--+-++-+---++-+--+--+-++-
++-++--+--+++----+++--+-++--++
--++---+++--+--++-++--++-+-++-
+-+----+-+++-+--+++--++--+--+-
+++---++-++---+++--+---+++-++-
-+--+-+--++-++--+--+-+-++++-+-
+---+--+-++--+-++-++--++-+-++-
-+--+-++-++--+-++-+-+-+----+-+
-++-+-++-++-+--

Also <math>x_{11n} = -x_n</math> (which was not forced by constraint). The subsequences group as follows:

617: 1 4 10 13 16 19 22 25 27 31 34 40 42 46 52 55 58 64

3478: 2 5 8 11 17 20 21 23 26 29 32 38 41 44 50 54 59 62 65

809: 18 37 45

3286: 9 36

873: 7 28 49

3222: 14 35 47 56

1458: 3 12 30 39 48 57

2637: 6 15 24 33 43 51 60 63

1266: 53

Length 688:

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++--+-++-+---+-++--+--+-+++
-+--+-++--+--+-++-++--+-++-++-
-+-++----++-++--+--+-++--++-++
+--++--+--+-++--+-++--++-+-+-+
+---+-++--++-+-++-+---+-++-++-
-+-++--+-++-+---++-+-++--+--+-
+--++--+-++-+++-+--+--+--+-+++
+---+-++--+--+-++-++---+++-+--
-++-+--+-++++---+-++--+--+-++-
++-++----++-++---+++--+--+++--
-++-+++--++--+-++-+----+++--++
-+-++---+-+-++-++--+-++--+--++
+--++--+-++-+---+--+-+++--+-+-
++-+--++--++---++-++--+-++--+-
-++++--+--+-++-++--+-++--+---+
++--+-++--+++---+-++-++--+-+--
-++-+-++--+--+-++-++--+-++-++-
-+-++--+--+-+++----+-++--++++-
+--+--++--+-++--++-+-+---++++-
+---++-+--+++---+-++-++--+--++
---++--+-++-+-+++----+++-+-++

This also satisfies <math>x_{7n} = -x_{11n}</math> which is interesting because it was not an original constraint.

The subsequences seem to group as follows (initial numbers are binary coded versions of the first part of each subsequence, the paired sequences are negatives of each other):

617: 1 4 10 16 19 25 31 34 40 46

3478: 2 5 8 17 20 23 32 38 41 47 50

873: 7 13 22 28 33 37 42 49 52

3222: 11 14 21 26 29 35 39 44

1458: 3 12 30 48

2637: 6 15 24 43 51

1833: 18 27 45

2262: 9 36

T m(x) = (+/-)T n(x)

2010-01-11T18:57:32Z

Mark Bennet: Analysis of 974 sequence

This sequence, of length 974, satisfies the following relations exactly:

<math>x_{2n} = -x_n</math>

<math>x_{5n} = -x_n</math>

<math>x_{13n} = -x_{11n}</math>

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++----++-++--+-++--+--+-+++
-+--+-+--++--+-++-++--+-++--+-
-+-++--+-++-+++-+--+-++--+--+-
++-++--+--+-++--+-++--++-+-+-+
+---+-++-++---+++--+--+-++-++-
-+--+--+-++-++--+--+-++-++--+-
++--+--+-++-++--++---++--+-+-+
++--+-++--++---++-+--++-++--+-
-+-++--+-++-++--+-++--++-+--+-
+--+++-+--+-++---++--++--+++-+
--+-+-+--+++-+-++----++-+++--+
-+--+-++--+-++-++--+-++--+--++
+---+-+--++++---+--+-+++---++-
++--+-++--+--+-++--+-++-++--+-
-+-++++---+-++--++-+-++--+--+-
++-+--+++-+--+--+-++-++--++---
-+-++-++-++----++-++---++++-+-
-+-++---+++--+-++--+--+-++-++-
+---+--+-++-++--++-+--+--+-++-
++-++--+--+++----+++--+-++--++
--+++--+-+--++-++-+---++-+--+-
+-++---++++--+--+++--+---++--+
+++---++-++---+++--+---+++-++-
-+-++-+-+-+--+--+--+-+-++++---
++--+-++--+--+-++-++-++--+-++-
-+-++-+---++-+-++-+---+-++---+
-++-+-++-++---+++--+-+-+--+-+-
++-++-+---++-+---++-+++----++-
-+-++++---++-+-++-+---+-++--++
-+-++-+---++-+--+--+-++-++--+-
++--++-+-+-+-++

As with the length 854 sequence <math>x_{11n} = -x_n</math>.

617: 1 4 10 13 16 19 22 25 27 31 34 40 42 46 52 55 58 64

3478: 2 5 8 11 17 20 21 23 26 29 32 38 41 44 50 54 59 62 65 68

809: 18 37 45 61 72

3286: 9 36 74

873: 7 28 49 70

3222: 14 35 47 56

1458: 3 12 30 39 48 57 66

2637: 6 15 24 33 43 51 60 69 73

Sporadic

242: 67

1266: 53 71

3661: 63

49 appears to be in the wrong place, but the 49-sequence is equal to the 7-sequence as far as position 19.

Length 854:

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++----++-++--+-++--++-+-++-
-+--+-+--++--+-++-++--+-++--+-
-+-++--+-++-+++-+--+-++--+--+-
++-++--+--+-++---+++--++-+-++-
+---+-++-++---+++--+--+-++-++-
-+-++--+-++-+---++---++-++--+-
++--+--+-++-++--++---++--+-+-+
++--+-++--++-+-++-+---+-++--+-
-+-++--+-++-++--+-++--++-+--+-
+-++-+-+--+-++---+++-++--+-++-
--+-+-+--+++-+-++--+--+-+++---
-+-++-++--+-++-++--+-++----+++
+---+--+-++++---+--+-++--++-+-
++-+--+++-+--+-++----++-++--+-
-+-++++---+-++--++-+-++--+--+-
++-+--+++-+--+--+-++-++--++---
-+-++-++-++----++-++---+++--++
-+-++---+-+-++-++--+--+-++--++
+--++--+-++-+---++-+--+--+-++-
++-++--+--+++----+++--+-++--++
--++---+++--+--++-++--++-+-++-
+-+----+-+++-+--+++--++--+--+-
+++---++-++---+++--+---+++-++-
-+--+-+--++-++--+--+-+-++++-+-
+---+--+-++--+-++-++--++-+-++-
-+--+-++-++--+-++-+-+-+----+-+
-++-+-++-++-+--

Also <math>x_{11n} = -x_n</math> (which was not forced by constraint). The subsequences group as follows:

617: 1 4 10 13 16 19 22 25 27 31 34 40 42 46 52 55 58 64

3478: 2 5 8 11 17 20 21 23 26 29 32 38 41 44 50 54 59 62 65

809: 18 37 45

3286: 9 36

873: 7 28 49

3222: 14 35 47 56

1458: 3 12 30 39 48 57

2637: 6 15 24 33 43 51 60 63

1266: 53

Length 688:

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++--+-++-+---+-++--+--+-+++
-+--+-++--+--+-++-++--+-++-++-
-+-++----++-++--+--+-++--++-++
+--++--+--+-++--+-++--++-+-+-+
+---+-++--++-+-++-+---+-++-++-
-+-++--+-++-+---++-+-++--+--+-
+--++--+-++-+++-+--+--+--+-+++
+---+-++--+--+-++-++---+++-+--
-++-+--+-++++---+-++--+--+-++-
++-++----++-++---+++--+--+++--
-++-+++--++--+-++-+----+++--++
-+-++---+-+-++-++--+-++--+--++
+--++--+-++-+---+--+-+++--+-+-
++-+--++--++---++-++--+-++--+-
-++++--+--+-++-++--+-++--+---+
++--+-++--+++---+-++-++--+-+--
-++-+-++--+--+-++-++--+-++-++-
-+-++--+--+-+++----+-++--++++-
+--+--++--+-++--++-+-+---++++-
+---++-+--+++---+-++-++--+--++
---++--+-++-+-+++----+++-+-++

This also satisfies <math>x_{7n} = -x_{11n}</math> which is interesting because it was not an original constraint.

The subsequences seem to group as follows (initial numbers are binary coded versions of the first part of each subsequence, the paired sequences are negatives of each other):

617: 1 4 10 16 19 25 31 34 40 46

3478: 2 5 8 17 20 23 32 38 41 47 50

873: 7 13 22 28 33 37 42 49 52

3222: 11 14 21 26 29 35 39 44

1458: 3 12 30 48

2637: 6 15 24 43 51

1833: 18 27 45

2262: 9 36

Talk:T m(x) = (+/-)T n(x)

2010-01-11T17:14:51Z

Mark Bennet: New page: The cases Tm(x)=±Tn(x)=±x and C=2 are providing some interesting structure when the values of m and n are primes (2 and 5 were a good choice, and 11 and 13 got added to the mix). It is a...

The cases Tm(x)=±Tn(x)=±x and C=2 are providing some interesting structure when the values of m and n are primes (2 and 5 were a good choice, and 11 and 13 got added to the mix). It is also possible to add other constraints of the form Tr(x)=±Ts(x) for primes r and s. What seems to happen is that the values on Tp(x) for other (unconstrained) primes adapt themselves to make the sequence work. So with the example sequence of length 854 this happens for the primes 3 and 7. It would be interesting to understand what would make a good set of primes to constrain, and whether there is any reason that particular choices of sign work well.

T m(x) = (+/-)T n(x)

2010-01-11T08:19:08Z

Mark Bennet: Subsequence analysis of sequence length 854

This sequence, of length 854, satisfies the following relations exactly:

<math>x_{2n} = -x_n</math>

<math>x_{5n} = -x_n</math>

<math>x_{13n} = -x_{11n}</math>

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++----++-++--+-++--++-+-++-
-+--+-+--++--+-++-++--+-++--+-
-+-++--+-++-+++-+--+-++--+--+-
++-++--+--+-++---+++--++-+-++-
+---+-++-++---+++--+--+-++-++-
-+-++--+-++-+---++---++-++--+-
++--+--+-++-++--++---++--+-+-+
++--+-++--++-+-++-+---+-++--+-
-+-++--+-++-++--+-++--++-+--+-
+-++-+-+--+-++---+++-++--+-++-
--+-+-+--+++-+-++--+--+-+++---
-+-++-++--+-++-++--+-++----+++
+---+--+-++++---+--+-++--++-+-
++-+--+++-+--+-++----++-++--+-
-+-++++---+-++--++-+-++--+--+-
++-+--+++-+--+--+-++-++--++---
-+-++-++-++----++-++---+++--++
-+-++---+-+-++-++--+--+-++--++
+--++--+-++-+---++-+--+--+-++-
++-++--+--+++----+++--+-++--++
--++---+++--+--++-++--++-+-++-
+-+----+-+++-+--+++--++--+--+-
+++---++-++---+++--+---+++-++-
-+--+-+--++-++--+--+-+-++++-+-
+---+--+-++--+-++-++--++-+-++-
-+--+-++-++--+-++-+-+-+----+-+
-++-+-++-++-+--

Also <math>x_{11n} = -x_n</math> (which was not forced by constraint). The subsequences group as follows:

617: 1 4 10 13 16 19 22 25 27 31 34 40 42 46 52 55 58 64

3478: 2 5 8 11 17 20 21 23 26 29 32 38 41 44 50 54 59 62 65

809: 18 37 45

3286: 9 36

873: 7 28 49

3222: 14 35 47 56

1458: 3 12 30 39 48 57

2637: 6 15 24 33 43 51 60 63

1266: 53

Length 688:

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++--+-++-+---+-++--+--+-+++
-+--+-++--+--+-++-++--+-++-++-
-+-++----++-++--+--+-++--++-++
+--++--+--+-++--+-++--++-+-+-+
+---+-++--++-+-++-+---+-++-++-
-+-++--+-++-+---++-+-++--+--+-
+--++--+-++-+++-+--+--+--+-+++
+---+-++--+--+-++-++---+++-+--
-++-+--+-++++---+-++--+--+-++-
++-++----++-++---+++--+--+++--
-++-+++--++--+-++-+----+++--++
-+-++---+-+-++-++--+-++--+--++
+--++--+-++-+---+--+-+++--+-+-
++-+--++--++---++-++--+-++--+-
-++++--+--+-++-++--+-++--+---+
++--+-++--+++---+-++-++--+-+--
-++-+-++--+--+-++-++--+-++-++-
-+-++--+--+-+++----+-++--++++-
+--+--++--+-++--++-+-+---++++-
+---++-+--+++---+-++-++--+--++
---++--+-++-+-+++----+++-+-++

This also satisfies <math>x_{7n} = -x_{11n}</math> which is interesting because it was not an original constraint.

The subsequences seem to group as follows (initial numbers are binary coded versions of the first part of each subsequence, the paired sequences are negatives of each other):

617: 1 4 10 16 19 25 31 34 40 46

3478: 2 5 8 17 20 23 32 38 41 47 50

873: 7 13 22 28 33 37 42 49 52

3222: 11 14 21 26 29 35 39 44

1458: 3 12 30 48

2637: 6 15 24 43 51

1833: 18 27 45

2262: 9 36

T m(x) = (+/-)T n(x)

2010-01-11T05:29:11Z

Mark Bennet:

This sequence, of length 688, satisfies the following relations exactly:

<math>x_{2n} = -x_n</math>

<math>x_{5n} = -x_n</math>

<math>x_{13n} = -x_{11n}</math>

0+--+-++--+--+-++-++--+-++-++-
-+-++--+--+-++-++--+-++--+--+-
++-++--+-++-+---+-++--+--+-+++
-+--+-++--+--+-++-++--+-++-++-
-+-++----++-++--+--+-++--++-++
+--++--+--+-++--+-++--++-+-+-+
+---+-++--++-+-++-+---+-++-++-
-+-++--+-++-+---++-+-++--+--+-
+--++--+-++-+++-+--+--+--+-+++
+---+-++--+--+-++-++---+++-+--
-++-+--+-++++---+-++--+--+-++-
++-++----++-++---+++--+--+++--
-++-+++--++--+-++-+----+++--++
-+-++---+-+-++-++--+-++--+--++
+--++--+-++-+---+--+-+++--+-+-
++-+--++--++---++-++--+-++--+-
-++++--+--+-++-++--+-++--+---+
++--+-++--+++---+-++-++--+-+--
-++-+-++--+--+-++-++--+-++-++-
-+-++--+--+-+++----+-++--++++-
+--+--++--+-++--++-+-+---++++-
+---++-+--+++---+-++-++--+--++
---++--+-++-+-+++----+++-+-++

This also satisfies <math>x_{7n} = -x_{11n}</math> which is interesting because it was not an original constraint.

The subsequences seem to group as follows (initial numbers are binary coded versions of the first part of each subsequence, the paired sequences are negatives of each other):

617: 1 4 10 16 19 25 31 34 40 46

3478: 2 5 8 17 20 23 32 38 41 47 50

873: 7 13 22 28 33 37 42 49 52

3222: 11 14 21 26 29 35 39 44

1458: 3 12 30 48

2637: 6 15 24 43 51

1833: 18 27 45

2262: 9 36

Experimental results

2010-01-10T22:38:46Z

Mark Bennet:

To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].

Perhaps we should have two kinds of subpages to this page: Pages about finding examples, and pages about analyzing them?

== Experimental data==
* [[The first 1124-sequence]] with discrepancy 2. ''Some more description''
* Other [[length 1124 sequences]] with discrepancy 2. ''Some more description''
* Some data about the problem with [[different upper and lower bound]]. ''Some more description''
* Sequences taking values in <math>\mathbb{T}</math>:
** [[4th roots of unity]]
** [[6th roots of unity]]
* [http://thomas1111.wordpress.com/2010/01/10/tables-for-a-c10-candidate/ A sequence of length 407] with discrepancy 2 such that <math>x_n=x_{32 n}</math> for every n. [[The HAP-subsequence structure of that sequence]].
* More [[T32-invariant sequences]].
* Long [[multiplicative sequences]].
* Long sequences satisfying [[T2(x) = -x]].
* Long sequences satisfying [[T2(x) = T5(x) = -x]]
* Long sequences satisfying [[T2(x) = -T3(x)]].

==Wish list==

* Find long/longest quasi-multiplicative sequences with some fixed group G, function <math>G\to \{-1,1\}</math> and maximal discrepancy C
** <math>G=C_6</math> and the function that sends 0,1 and 2 to 1 (because this seems to be a good choice)
* Do a "Mark-Bennet-style analysis" of one of the new 1124-sequences. [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4827] Also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4842 done] (by Mark Bennet).
*. Take a moderately large k and search for the longest sequence of discrepancy 2 that's constructed as follows. First, pick a completely multiplicative function f to the group <math>C_{2k}</math>. Then set <math>x_n</math> to be 1 if f(n) lies between 0 and k-1, and -1 if f(n) lies between k and 2k-1. Alec has already [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4563 done this for k=1] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4734 partially done it for k=3].
*Search for the longest sequence of discrepancy 2 with the property that <math>x_n=x_{32n}</math> for every n. The motivation for this is to produce a fundamentally different class of examples (different because their group structure would include an element of order 5). It's not clear that it will work, since 32 is a fairly large number. However, if you've chosen <math>x_{32n}</math> then that will have some influence on several other choices, such as <math>x_{4n},x_{8n}</math> and <math>x_{16n}</math>, so maybe it will lead to something interesting. Alec [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4873 has made a start on this] and an [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4874 initial investigation] suggests that the sequence he has found does indeed have some <math>C_{10}</math>-related structure.
*Here's another experiment that should be pretty easy to program and might yield something interesting. It's to look at the how the discrepancy appears to grow when you define a sequence using a greedy algorithm. I say "a" greedy algorithm because there are various algorithms that could reasonably be described as greedy. Here are a few.

<blockquote>
1. For each n let <math>x_n</math> be chosen so as to minimize the discrepancy so far, given the choices already made for <math>x_1,\dots,x_{n-1}</math>. (If this does not uniquely determine <math>x_n</math> then choose it arbitrarily, or randomly, or according to some simple rule like always equalling 1.)
</blockquote>

<blockquote>
2. Same as 1 but with additional constraints, in the hope that these make the sequence more likely to be good. For instance, one might insist that <math>x_{2k}=x_{3k}</math> for every k. Here, when choosing <math>x_n</math> one would probably want to minimize the discrepancy up to <math>x_{n+k}</math> if <math>x_{n+1},\dots,x_{n+k}</math> had already been chosen. Another obvious constraint to try is complete multiplicativity.
</blockquote>

<blockquote>
3. A greedy algorithm of sorts, but this time trying to minimize a different parameter. The first algorithm will do this: when you pick <math>x_n</math> you look, for each factor d of n, at the partial sum along the multiples of d up to but not including n. This will give you a set A of numbers (the possible partial sums). If max(A) is greater than max(-A) then you set <math>x_n=-1</math>, if max(-A) is greater than max(A) then you let <math>x_n=1</math>, and if they are equal then you make the decision according to some rule that seems sensible. But it might be that you would end up with a slower-growing discrepancy if you regarded A as a multiset and made the decision on some other basis. For instance, you could take the sum of <math>2^k</math> over all positive elements <math>k\in A</math> (with multiplicity) and the sum of <math>2^{-k}</math> over all negative elements and choose <math>x_n</math> according to which was bigger. Although that wouldn't minimize the discrepancy at each stage, it might make the sequence better for future development because it wouldn't sacrifice the needs of an overwhelming majority to those of a few rogue elements.

The motivation for these experiments is to see whether they, or some variants, appear to lead to sublogarithmic growth. If they do, then we could start trying to prove rigorously that sublogarithmic growth is possible. I still think that a function that arises in nature and satisfies f(1124)=2 ought to be sublogarithmic.
</blockquote>

*What happens if one applies a backtracking algorithm to try to extend the following discrepancy-2 sequence, which satisfies <math>x_{2n}=-x_n</math> for every n, to a much longer discrepancy-2 sequence: + - - + - + + - - + + - + - + + - + - - + - - + + - - + + - + - - + - - + + + + - - - + + + - - + - + + - + - - + - ? This question has been answered [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4893 in the comments following the asking of the question on the blog].

* Investigate what happens if our HAPs are restricted to allow differences divisible only by 2 or 3 [and then other sets of primes including 2] - {2,3,5,7} would be interesting - is there an infinite sequence of discrepancy 2 in these simple cases - is it easy to find an infinite sequence with finite discrepancy in these cases? [for sets of odd primes, take a sequence which is 1 on odd numbers, -1 on even numbers. Including 2 is the non-trivial case]. It is possible that completely multiplicative sequences could be found for some of these cases.

* ... you are welcome to add more.

Experimental results

2010-01-10T18:16:12Z

Mark Bennet:

To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].

Perhaps we should have two kinds of subpages to this page: Pages about finding examples, and pages about analyzing them?

== Experimental data==
* [[The first 1124-sequence]] with discrepancy 2. ''Some more description''
* Other [[length 1124 sequences]] with discrepancy 2. ''Some more description''
* Some data about the problem with [[different upper and lower bound]]. ''Some more description''
* Sequences taking values in <math>\mathbb{T}</math>:
** [[4th roots of unity]]
** [[6th roots of unity]]
* [http://thomas1111.wordpress.com/2010/01/10/tables-for-a-c10-candidate/ A sequence of length 407] with discrepancy 2 such that <math>x_n=x_{32 n}</math> for every n. [[The HAP-subsequence structure of that sequence]].
* More [[T32-invariant sequences]].
* Long [[multiplicative sequences]].
* Long sequences satisfying [[T2(x) = -T(x)]]. <em>This should surely say T2(x)=-x, but I don't seem to be able to change the title of the page.</em>

==Wish list==

* Find long/longest quasi-multiplicative sequences with some fixed group G, function <math>G\to \{-1,1\}</math> and maximal discrepancy C
** <math>G=C_6</math> and the function that sends 0,1 and 2 to 1 (because this seems to be a good choice)
* Do a "Mark-Bennet-style analysis" of one of the new 1124-sequences. [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4827] Also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4842 done] (by Mark Bennet).
*. Take a moderately large k and search for the longest sequence of discrepancy 2 that's constructed as follows. First, pick a completely multiplicative function f to the group <math>C_{2k}</math>. Then set <math>x_n</math> to be 1 if f(n) lies between 0 and k-1, and -1 if f(n) lies between k and 2k-1. Alec has already [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4563 done this for k=1] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4734 partially done it for k=3].
*Search for the longest sequence of discrepancy 2 with the property that <math>x_n=x_{32n}</math> for every n. The motivation for this is to produce a fundamentally different class of examples (different because their group structure would include an element of order 5). It's not clear that it will work, since 32 is a fairly large number. However, if you've chosen <math>x_{32n}</math> then that will have some influence on several other choices, such as <math>x_{4n},x_{8n}</math> and <math>x_{16n}</math>, so maybe it will lead to something interesting. Alec [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4873 has made a start on this] and an [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4874 initial investigation] suggests that the sequence he has found does indeed have some <math>C_{10}</math>-related structure.
*Here's another experiment that should be pretty easy to program and might yield something interesting. It's to look at the how the discrepancy appears to grow when you define a sequence using a greedy algorithm. I say "a" greedy algorithm because there are various algorithms that could reasonably be described as greedy. Here are a few.

<blockquote>
1. For each n let <math>x_n</math> be chosen so as to minimize the discrepancy so far, given the choices already made for <math>x_1,\dots,x_{n-1}</math>. (If this does not uniquely determine <math>x_n</math> then choose it arbitrarily, or randomly, or according to some simple rule like always equalling 1.)
</blockquote>

<blockquote>
2. Same as 1 but with additional constraints, in the hope that these make the sequence more likely to be good. For instance, one might insist that <math>x_{2k}=x_{3k}</math> for every k. Here, when choosing <math>x_n</math> one would probably want to minimize the discrepancy up to <math>x_{n+k}</math> if <math>x_{n+1},\dots,x_{n+k}</math> had already been chosen. Another obvious constraint to try is complete multiplicativity.
</blockquote>

<blockquote>
3. A greedy algorithm of sorts, but this time trying to minimize a different parameter. The first algorithm will do this: when you pick <math>x_n</math> you look, for each factor d of n, at the partial sum along the multiples of d up to but not including n. This will give you a set A of numbers (the possible partial sums). If max(A) is greater than max(-A) then you set <math>x_n=-1</math>, if max(-A) is greater than max(A) then you let <math>x_n=1</math>, and if they are equal then you make the decision according to some rule that seems sensible. But it might be that you would end up with a slower-growing discrepancy if you regarded A as a multiset and made the decision on some other basis. For instance, you could take the sum of <math>2^k</math> over all positive elements <math>k\in A</math> (with multiplicity) and the sum of <math>2^{-k}</math> over all negative elements and choose <math>x_n</math> according to which was bigger. Although that wouldn't minimize the discrepancy at each stage, it might make the sequence better for future development because it wouldn't sacrifice the needs of an overwhelming majority to those of a few rogue elements.

The motivation for these experiments is to see whether they, or some variants, appear to lead to sublogarithmic growth. If they do, then we could start trying to prove rigorously that sublogarithmic growth is possible. I still think that a function that arises in nature and satisfies f(1124)=2 ought to be sublogarithmic.
</blockquote>

*What happens if one applies a backtracking algorithm to try to extend the following discrepancy-2 sequence, which satisfies <math>x_{2n}=-x_n</math> for every n, to a much longer discrepancy-2 sequence: + - - + - + + - - + + - + - + + - + - - + - - + + - - + + - + - - + - - + + + + - - - + + + - - + - + + - + - - + - ?

* Investigate what happens if our HAPs are restricted to allow differences divisible only by 2 or 3 [and then other sets of primes including 2] - {2,3,5,7} would be interesting - is there an infinite sequence of discrepancy 2 in these simple cases - is it easy to find an infinite sequence with finite discrepancy in these cases? [for sets of odd primes, take a sequence which is 1 on odd numbers, -1 on even numbers, including 2 is the non-trivial case]

* ... you are welcome to add more.

Experimental results

2010-01-10T18:15:23Z

Mark Bennet: An additional wish for investigation of finite sets of primes including 2

To return to the main Polymath5 page, click [[The Erdős discrepancy problem|here]].

Perhaps we should have two kinds of subpages to this page: Pages about finding examples, and pages about analyzing them?

== Experimental data==
* [[The first 1124-sequence]] with discrepancy 2. ''Some more description''
* Other [[length 1124 sequences]] with discrepancy 2. ''Some more description''
* Some data about the problem with [[different upper and lower bound]]. ''Some more description''
* Sequences taking values in <math>\mathbb{T}</math>:
** [[4th roots of unity]]
** [[6th roots of unity]]
* [http://thomas1111.wordpress.com/2010/01/10/tables-for-a-c10-candidate/ A sequence of length 407] with discrepancy 2 such that <math>x_n=x_{32 n}</math> for every n. [[The HAP-subsequence structure of that sequence]].
* More [[T32-invariant sequences]].
* Long [[multiplicative sequences]].
* Long sequences satisfying [[T2(x) = -T(x)]]. <em>This should surely say T2(x)=-x, but I don't seem to be able to change the title of the page.</em>

==Wish list==

* Find long/longest quasi-multiplicative sequences with some fixed group G, function <math>G\to \{-1,1\}</math> and maximal discrepancy C
** <math>G=C_6</math> and the function that sends 0,1 and 2 to 1 (because this seems to be a good choice)
* Do a "Mark-Bennet-style analysis" of one of the new 1124-sequences. [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4827] Also [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4842 done] (by Mark Bennet).
*. Take a moderately large k and search for the longest sequence of discrepancy 2 that's constructed as follows. First, pick a completely multiplicative function f to the group <math>C_{2k}</math>. Then set <math>x_n</math> to be 1 if f(n) lies between 0 and k-1, and -1 if f(n) lies between k and 2k-1. Alec has already [http://gowers.wordpress.com/2009/12/17/erdoss-discrepancy-problem/#comment-4563 done this for k=1] and [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4734 partially done it for k=3].
*Search for the longest sequence of discrepancy 2 with the property that <math>x_n=x_{32n}</math> for every n. The motivation for this is to produce a fundamentally different class of examples (different because their group structure would include an element of order 5). It's not clear that it will work, since 32 is a fairly large number. However, if you've chosen <math>x_{32n}</math> then that will have some influence on several other choices, such as <math>x_{4n},x_{8n}</math> and <math>x_{16n}</math>, so maybe it will lead to something interesting. Alec [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4873 has made a start on this] and an [http://gowers.wordpress.com/2010/01/09/erds-discrepancy-problem-continued/#comment-4874 initial investigation] suggests that the sequence he has found does indeed have some <math>C_{10}</math>-related structure.
*Here's another experiment that should be pretty easy to program and might yield something interesting. It's to look at the how the discrepancy appears to grow when you define a sequence using a greedy algorithm. I say "a" greedy algorithm because there are various algorithms that could reasonably be described as greedy. Here are a few.

<blockquote>
1. For each n let <math>x_n</math> be chosen so as to minimize the discrepancy so far, given the choices already made for <math>x_1,\dots,x_{n-1}</math>. (If this does not uniquely determine <math>x_n</math> then choose it arbitrarily, or randomly, or according to some simple rule like always equalling 1.)
</blockquote>

<blockquote>
2. Same as 1 but with additional constraints, in the hope that these make the sequence more likely to be good. For instance, one might insist that <math>x_{2k}=x_{3k}</math> for every k. Here, when choosing <math>x_n</math> one would probably want to minimize the discrepancy up to <math>x_{n+k}</math> if <math>x_{n+1},\dots,x_{n+k}</math> had already been chosen. Another obvious constraint to try is complete multiplicativity.
</blockquote>

<blockquote>
3. A greedy algorithm of sorts, but this time trying to minimize a different parameter. The first algorithm will do this: when you pick <math>x_n</math> you look, for each factor d of n, at the partial sum along the multiples of d up to but not including n. This will give you a set A of numbers (the possible partial sums). If max(A) is greater than max(-A) then you set <math>x_n=-1</math>, if max(-A) is greater than max(A) then you let <math>x_n=1</math>, and if they are equal then you make the decision according to some rule that seems sensible. But it might be that you would end up with a slower-growing discrepancy if you regarded A as a multiset and made the decision on some other basis. For instance, you could take the sum of <math>2^k</math> over all positive elements <math>k\in A</math> (with multiplicity) and the sum of <math>2^{-k}</math> over all negative elements and choose <math>x_n</math> according to which was bigger. Although that wouldn't minimize the discrepancy at each stage, it might make the sequence better for future development because it wouldn't sacrifice the needs of an overwhelming majority to those of a few rogue elements.

The motivation for these experiments is to see whether they, or some variants, appear to lead to sublogarithmic growth. If they do, then we could start trying to prove rigorously that sublogarithmic growth is possible. I still think that a function that arises in nature and satisfies f(1124)=2 ought to be sublogarithmic.
</blockquote>

*What happens if one applies a backtracking algorithm to try to extend the following discrepancy-2 sequence, which satisfies <math>x_{2n}=-x_n</math> for every n, to a much longer discrepancy-2 sequence: + - - + - + + - - + + - + - + + - + - - + - - + + - - + + - + - - + - - + + + + - - - + + + - - + - + + - + - - + - ?

4. Investigate what happens if our HAPs are restricted to allow differences divisible only by 2 or 3 [and then other sets of primes including 2] - {2,3,5,7} would be interesting - is there an infinite sequence of discrepancy 2 in these simple cases - is it easy to find an infinite sequence with finite discrepancy in these cases? [for sets of odd primes, take a sequence which is 1 on odd numbers, -1 on even numbers, including 2 is the non-trivial case]

* ... you are welcome to add more.

Talk:Kolmogorov complexity

2009-08-04T20:44:31Z

Mark Bennet: New page: Simple observation. As with algorithms for compressing files for data transmission, there may be a number of different ways of setting up a Turing Machine to do the job, and different mach...

Simple observation. As with algorithms for compressing files for data transmission, there may be a number of different ways of setting up a Turing Machine to do the job, and different machines may give different sets of simple/complex numbers. But in order to specify, one has then to identify and describe the Turing Machine which is being invoked, and this reduces the efficiency of the process.

Talk:Imo 2009 q6

2009-07-25T17:18:43Z

Mark Bennet: Adding reference to proof #5

The approach adopted in proof #1 is 'let's make as much progress as possible, and then show that we can do an extra step'. It introduces an observation fundamental to a number of successful strategies- that if I can pass k mines in k leaps (with k>0), I have only n-k-1 mines left to jump and n-k leaps to do it. So if I can do smaller problem, I can do this one - which sets up an induction. In proof #1 this is used to provide constraints on an impossible minefield, and then the number of options available for paths is shown to overwhelm the constraints. This is the most sophisticated proof so far, in that it does not give the longest leap a special status. It looks set up to deal with more challenging generalisations of the problem.

Proof #2 uses a greedy approach - try to make the longest leap. Case 4 of proof #2 is akin to the approach in proof #1, though it is set up differently. The description of the approach in proof #2 suggests that there are essentially two cases to deal with (though the trivial case where the induction works might be considered a third) and proof #3 gives a two case approach which was discovered by programming proof #2 and being careful over the details which is set out here [http://www.erisian.com.au/wordpress/2009/07/23/solving-hard-maths-olympiad-problems].

The discussion on the Mathlinks Math Forum here [http://www.mathlinks.ro/Forum/viewtopic.php?t=289051] has another proof a bit similar to #2 where the inductive step is to remove the mine closest to the beginning (the proof by qwerty414 as stated has it at the end) and to look at two cases: the first where doing the longest leap first lands on one of the remaining mines, and the second where it doesn't. An 'end' version of this now appears as proof #5 (which is very similar to proof #4).

Proof #2 has a 'working from both ends' feel - the dual approach in proof #4 uses the inductive hypothesis to get as far as possible without using the longest leap, and this automatically collapses cases 2.2 and 3 of proof #2. What can go wrong? Well we can land on the last mine (we know we can dodge all but one) - and we swap in the longest leap to clear it, or we land on a mine with the last leap and still have some to clear - in which case the counting argument of proof #2 case 4 is used.

Useful counterexamples to false proofs can be constructed by putting all the mines together in some part of the minefield. For the jump set {1,2 ... n} this forces the longest leap, so the proof needs to make sure that the longest leap is available at this point. It is also possible to mine all but one of the possible first leaps (or last ones).

Talk:Imo 2009 q6

2009-07-24T08:56:43Z

Mark Bennet:

The approach adopted in proof #1 is 'let's make as much progress as possible, and then show that we can do an extra step'. It introduces an observation fundamental to a number of successful strategies- that if I can pass k mines in k leaps (with k>0), I have only n-k-1 mines left to jump and n-k leaps to do it. So if I can do smaller problem, I can do this one - which sets up an induction. In proof #1 this is used to provide constraints on an impossible minefield, and then the number of options available for paths is shown to overwhelm the constraints. This is the most sophisticated proof so far, in that it does not give the longest leap a special status. It looks set up to deal with more challenging generalisations of the problem.

Proof #2 uses a greedy approach - try to make the longest leap. Case 4 of proof #2 is akin to the approach in proof #1, though it is set up differently. The description of the approach in proof #2 suggests that there are essentially two cases to deal with (though the trivial case where the induction works might be considered a third) and proof #3 gives a two case approach which was discovered by programming proof #2 and being careful over the details which is set out here [http://www.erisian.com.au/wordpress/2009/07/23/solving-hard-maths-olympiad-problems].

The discussion on the Mathlinks Math Forum here [http://www.mathlinks.ro/Forum/viewtopic.php?t=289051] has another proof a bit similar to #2 where the inductive step is to remove the mine closest to the beginning (the proof by qwerty414 as stated has it at the end) and to look at two cases: the first where doing the longest leap first lands on one of the remaining mines, and the second where it doesn't.

Proof #2 has a 'working from both ends' feel - the dual approach in proof #4 uses the inductive hypothesis to get as far as possible without using the longest leap, and this automatically collapses cases 2.2 and 3 of proof #2. What can go wrong? Well we can land on the last mine (we know we can dodge all but one) - and we swap in the longest leap to clear it, or we land on a mine with the last leap and still have some to clear - in which case the counting argument of proof #2 case 4 is used.

Useful counterexamples to false proofs can be constructed by putting all the mines together in some part of the minefield. For the jump set {1,2 ... n} this forces the longest leap, so the proof needs to make sure that the longest leap is available at this point. It is also possible to mine all but one of the possible first leaps (or last ones).

Talk:Imo 2009 q6

2009-07-23T08:36:10Z

Mark Bennet: New page: It seems to me that proof #1 says 'let's make as much progress as possible', and by working with sets of partial paths extends the counting approach used in proof #2 case 4 to do more work...

It seems to me that proof #1 says 'let's make as much progress as possible', and by working with sets of partial paths extends the counting approach used in proof #2 case 4 to do more work. It might generalise more easily eg in more dimensions, where the blocking sets might be more complex, and working back from the end might not be so easy to achieve nicely. Proof #2 has been converted into an algorithm and programmed in Mathematica (unchecked by me) [http://pastebin.com/f13130032] by jc, whereas proof #1 is non constructive. Proof #1 gives no special status to the longest leap.

The discussion on the Mathlinks Math Forum here [http://www.mathlinks.ro/Forum/viewtopic.php?t=289051] has another proof a bit similar to #2 where the inductive step is to remove the mine closest to the beginning (the proof by qwerty414 as stated has it at the end) and to look at two cases: the first where doing the longest leap first lands on one of the remaining mines, and the second where it doesn't. This seems to reduce the number of cases, but the argument is not quite so straightforward.

Imo 2009 q6

2009-07-23T06:59:40Z

Mark Bennet: /* Notation */

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

In proof 2 I have used 'mines'. I refer to the possibilities for the grasshopper as leaps, and to the actual components of a path through the minefield as jumps. So the longest leap can be the first or second or third jump (etc). I refer to an unmined space as a 'clear space'. Please feel free to suggest better terms/edit for consistency.

== Proof #1 ==

We induct on n, assuming that $latex n > 2$ and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.

Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine (by hypothesis - jumping the remaining n-1 mines with n leaps). We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)

Imo 2009 q6

2009-07-23T06:53:38Z

Mark Bennet: /* Proof #2 */

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

== Proof #1 ==

We induct on n, assuming that $latex n > 2$ and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.

Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine (by hypothesis - jumping the remaining n-1 mines with n leaps). We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)

Imo 2009 q6

2009-07-23T06:47:50Z

Mark Bennet: /* Proof #2 */

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

== Proof #1 ==

We induct on n, assuming that $latex n > 2$ and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.

Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine. We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)

Imo 2009 q6

2009-07-23T06:41:34Z

Mark Bennet: /* Proof #2 */

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

== Proof #1 ==

We induct on n, assuming that $latex n > 2$ and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the largest leap.

Case 1: If the largest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the largest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the largest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine. We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)

Imo 2009 q6

2009-07-23T06:38:27Z

Mark Bennet: /* Proof #2 */

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

== Proof #1 ==

We induct on n, assuming that $latex n > 2$ and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

PROOF

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the largest leap.

Case 1: If the largest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the largest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

2.1 If this arrangement also avoids the mine we removed, we are done.

2.2 If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the largest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine. We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)

Imo 2009 q6

2009-07-23T06:33:08Z

Mark Bennet: /* Proof #2 */

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

== Proof #1 ==

We induct on n, assuming that $latex n > 2$ and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter jumps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

PROOF

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the largest leap.

Case 1: If the largest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the largest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).
2.1 If this arrangement also avoids the mine we removed, we are done.
2.2 If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the largest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine. We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)