Why a bounded increasing potential is not enough for this balancing process

ghosttype_·Mar 19, 2025(edited)

The sum of squares seems to increase at every step. But a bounded increasing sequence can converge, so I don't think that alone proves an entry eventually reaches

n/2

. What closes the argument? Problem: Let

A_{0} = (a_{1}, \ldots, a_{n})

be a finite sequence of real numbers. For each

k \geq 0

, from the sequence

A_{k} = (x_{1}, \ldots, x_{n})

we construct a new sequence

A_{k+1}

in the following way. 1. We choose a partition

\{1, \ldots, n\} = I \cup J

, where

I

and

J

are two disjoint sets, such that the expression

\left|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}\right|

attains the smallest possible value. (We allow the sets

I

J

to be empty; in this case the corresponding sum is

0

.) If there are several such partitions, one is chosen arbitrarily. 2. We set

A_{k+1} = (y_{1}, \ldots, y_{n})

, where

y_{i} = x_{i} + 1

i \in I

, and

y_{i} = x_{i} - 1

i \in J

. Prove that for some

k

, the sequence

A_{k}

contains an element

x

such that

|x| \geq n / 2

. Source: IMO 2007 Shortlist · MNET-06PF

Open MNET-06PF in the question bank →

5 replies

parry_this·Mar 19, 2025(edited)

Assume every entry always stays in

(-n/2,n/2)

. Each coordinate is its starting real value plus an integer. That leaves only finitely many possible states.

ghosttype_·Mar 20, 2025(edited)

Ah, the coordinates aren't arbitrary reals anymore. I was treating the reachable set as the whole box.

savefile_07·Mar 20, 2025(edited)

For the increase, first prove that numbers with absolute values below

a

admit signs whose signed sum has absolute value below

a

. Add terms one at a time, choosing the sign to oppose the current sum. The absolute value becomes a difference of two numbers in

[0,a)

parry_this·Mar 20, 2025(edited)

With

a=n/2

, the minimizing partition has discrepancy

D

with

|D|<n/2

. The change in

\sum x_i^2

n+2D>0

, regardless of which minimizing partition was chosen.

ghosttype_·Mar 22, 2025(edited)

So any infinite run inside the box would repeat a state, whereas its squared norm strictly increases. That is the contradiction, without needing a uniform positive increment.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…

Why a bounded increasing potential is not enough for this balancing process

ghosttype_·Mar 19, 2025(edited)

The sum of squares seems to increase at every step. But a bounded increasing sequence can converge, so I don't think that alone proves an entry eventually reaches

n/2

. What closes the argument? Problem: Let

A_{0} = (a_{1}, \ldots, a_{n})

be a finite sequence of real numbers. For each

k \geq 0

, from the sequence

A_{k} = (x_{1}, \ldots, x_{n})

we construct a new sequence

A_{k+1}

in the following way. 1. We choose a partition

\{1, \ldots, n\} = I \cup J

, where

I

and

J

are two disjoint sets, such that the expression

\left|\sum_{i \in I} x_{i} - \sum_{j \in J} x_{j}\right|

attains the smallest possible value. (We allow the sets

I

J

to be empty; in this case the corresponding sum is

0

.) If there are several such partitions, one is chosen arbitrarily. 2. We set

A_{k+1} = (y_{1}, \ldots, y_{n})

, where

y_{i} = x_{i} + 1

i \in I

, and

y_{i} = x_{i} - 1

i \in J

. Prove that for some

k

, the sequence

A_{k}

contains an element

x

such that

|x| \geq n / 2

. Source: IMO 2007 Shortlist · MNET-06PF

Open MNET-06PF in the question bank →

5 replies

parry_this·Mar 19, 2025(edited)

Assume every entry always stays in

(-n/2,n/2)

. Each coordinate is its starting real value plus an integer. That leaves only finitely many possible states.

ghosttype_·Mar 20, 2025(edited)

Ah, the coordinates aren't arbitrary reals anymore. I was treating the reachable set as the whole box.

savefile_07·Mar 20, 2025(edited)

For the increase, first prove that numbers with absolute values below

a

admit signs whose signed sum has absolute value below

a

. Add terms one at a time, choosing the sign to oppose the current sum. The absolute value becomes a difference of two numbers in

[0,a)

parry_this·Mar 20, 2025(edited)

With

a=n/2

, the minimizing partition has discrepancy

D

with

|D|<n/2

. The change in

\sum x_i^2

n+2D>0

, regardless of which minimizing partition was chosen.

ghosttype_·Mar 22, 2025(edited)

So any infinite run inside the box would repeat a state, whereas its squared norm strictly increases. That is the contradiction, without needing a uniform positive increment.