Maths Olympiad Prep

Library / /27 of 27

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Croatia

A finite number of real numbers are ordered around a circle, and each number is coloured red, white or blue. Each red number is twice smaller than the sum of its two adjacent numbers, each white number is equal to the sum of its two adjacent numbers, and each blue number is twice larger than the sum of its two adjacent numbers. Let ww be the sum of all white numbers, and bb be the sum of all blue numbers, where both ww and bb are not 00.
Determine the ratio wb\frac{w}{b}.

Solution

Let the numbers be a1,a2,,ana_1, a_2, \ldots, a_n arranged around a circle. Each aia_i is colored red, white, or blue.

Let RR, WW, BB be the sets of indices of red, white, and blue numbers, respectively.

- For red aia_i: ai=12(ai1+ai+1)a_i = \frac{1}{2}(a_{i-1} + a_{i+1}) (since it is twice smaller than the sum of its neighbors).
- For white aia_i: ai=ai1+ai+1a_i = a_{i-1} + a_{i+1}.
- For blue aia_i: ai=2(ai1+ai+1)a_i = 2(a_{i-1} + a_{i+1}) (since it is twice larger than the sum of its neighbors).

Let w=iWaiw = \sum_{i \in W} a_i, b=iBaib = \sum_{i \in B} a_i.

Let S=i=1naiS = \sum_{i=1}^n a_i be the total sum.

Let us sum aia_i over all ii:

S=iRai+iWai+iBaiS = \sum_{i \in R} a_i + \sum_{i \in W} a_i + \sum_{i \in B} a_i

But for each color, we can write aia_i in terms of its neighbors:

iRai=12iR(ai1+ai+1)\sum_{i \in R} a_i = \frac{1}{2} \sum_{i \in R} (a_{i-1} + a_{i+1})
iWai=iW(ai1+ai+1)\sum_{i \in W} a_i = \sum_{i \in W} (a_{i-1} + a_{i+1})
iBai=2iB(ai1+ai+1)\sum_{i \in B} a_i = 2 \sum_{i \in B} (a_{i-1} + a_{i+1})

So,

S=12iR(ai1+ai+1)+iW(ai1+ai+1)+2iB(ai1+ai+1)S = \frac{1}{2} \sum_{i \in R} (a_{i-1} + a_{i+1}) + \sum_{i \in W} (a_{i-1} + a_{i+1}) + 2 \sum_{i \in B} (a_{i-1} + a_{i+1})

But iX(ai1+ai+1)\sum_{i \in X} (a_{i-1} + a_{i+1}) is the sum over all neighbors of XX.

Since the numbers are arranged in a circle, for each aja_j, the number of times it appears as a neighbor is equal to the number of times jj is adjacent to a member of RR, WW, or BB.

For each aja_j, let rjr_j be the number of red neighbors, wjw_j the number of white neighbors, bjb_j the number of blue neighbors. Since the circle is undirected, each aja_j has two neighbors, so rj+wj+bj=2r_j + w_j + b_j = 2 for each jj.

But summing over all ii in RR, WW, BB:

iR(ai1+ai+1)=j=1nrjaj\sum_{i \in R} (a_{i-1} + a_{i+1}) = \sum_{j=1}^n r_j a_j
iW(ai1+ai+1)=j=1nwjaj\sum_{i \in W} (a_{i-1} + a_{i+1}) = \sum_{j=1}^n w_j a_j
iB(ai1+ai+1)=j=1nbjaj\sum_{i \in B} (a_{i-1} + a_{i+1}) = \sum_{j=1}^n b_j a_j

So,

S=12j=1nrjaj+j=1nwjaj+2j=1nbjajS = \frac{1}{2} \sum_{j=1}^n r_j a_j + \sum_{j=1}^n w_j a_j + 2 \sum_{j=1}^n b_j a_j
=j=1n(12rj+wj+2bj)aj= \sum_{j=1}^n \left( \frac{1}{2} r_j + w_j + 2 b_j \right) a_j

But rj+wj+bj=2r_j + w_j + b_j = 2, so wj=2rjbjw_j = 2 - r_j - b_j.

So,

12rj+wj+2bj=12rj+(2rjbj)+2bj=212rjbj+2bj=212rj+bj\frac{1}{2} r_j + w_j + 2 b_j = \frac{1}{2} r_j + (2 - r_j - b_j) + 2 b_j = 2 - \frac{1}{2} r_j - b_j + 2 b_j = 2 - \frac{1}{2} r_j + b_j

Therefore,

S=j=1n(212rj+bj)ajS = \sum_{j=1}^n (2 - \frac{1}{2} r_j + b_j) a_j

But S=j=1najS = \sum_{j=1}^n a_j.

So,

j=1naj=j=1n(212rj+bj)aj\sum_{j=1}^n a_j = \sum_{j=1}^n (2 - \frac{1}{2} r_j + b_j) a_j

    j=1n(112rj+bj)aj=0\implies \sum_{j=1}^n (1 - \frac{1}{2} r_j + b_j) a_j = 0

Now, group the sum by color:

- For aja_j red: aja_j is red, so jRj \in R.
- For aja_j white: jWj \in W.
- For aja_j blue: jBj \in B.

For aja_j red: aja_j has rjr_j red neighbors, wjw_j white neighbors, bjb_j blue neighbors, with rj+wj+bj=2r_j + w_j + b_j = 2.
But since the coloring is arbitrary, but the sum is over all jj.

But let's try a small example to get the ratio.

Suppose there are only white and blue numbers (since ww and bb are both nonzero, and the problem is symmetric, we can try with only white and blue numbers).

Let us try with 2 white and 2 blue numbers, arranged alternately: w1,b1,w2,b2w_1, b_1, w_2, b_2.

Let a1=w1a_1 = w_1 (white), a2=b1a_2 = b_1 (blue), a3=w2a_3 = w_2 (white), a4=b2a_4 = b_2 (blue).

For white: ai=ai1+ai+1a_i = a_{i-1} + a_{i+1}
For blue: ai=2(ai1+ai+1)a_i = 2(a_{i-1} + a_{i+1})

Let us write the equations:

a1=a4+a2a_1 = a_4 + a_2
a2=2(a1+a3)a_2 = 2(a_1 + a_3)
a3=a2+a4a_3 = a_2 + a_4
a4=2(a3+a1)a_4 = 2(a_3 + a_1)

Let us denote a1=xa_1 = x, a2=ya_2 = y, a3=za_3 = z, a4=ta_4 = t.

So:
x=t+yx = t + y
y=2(x+z)y = 2(x + z)
z=y+tz = y + t
t=2(z+x)t = 2(z + x)

From x=t+yx = t + y and z=y+tz = y + t, so x=t+yx = t + y, z=y+tz = y + t.
So x=zx = z.

Let x=z=sx = z = s.

Then y=2(x+z)=4sy = 2(x + z) = 4s
t=2(z+x)=4st = 2(z + x) = 4s

So x=t+y=4s+4s=8sx = t + y = 4s + 4s = 8s, so s=0s = 0 unless s=0s = 0.

But then all numbers are zero, which is not allowed.

Try with 1 white and 2 blue numbers: a1a_1 (white), a2a_2 (blue), a3a_3 (blue).

a1=a3+a2a_1 = a_3 + a_2
a2=2(a1+a3)a_2 = 2(a_1 + a_3)
a3=2(a2+a1)a_3 = 2(a_2 + a_1)

Let a1=xa_1 = x, a2=ya_2 = y, a3=za_3 = z.

x=y+zx = y + z
y=2(x+z)y = 2(x + z)
z=2(y+x)z = 2(y + x)

From x=y+zx = y + z, so y=xzy = x - z.

Plug into y=2(x+z)y = 2(x + z):
xz=2(x+z)x - z = 2(x + z)
xz=2x+2zx - z = 2x + 2z
xz2x2z=0x - z - 2x - 2z = 0
x3z=0-x - 3z = 0
x=3zx = -3z

So y=xz=3zz=4zy = x - z = -3z - z = -4z

Now z=2(y+x)=2(4z3z)=2(7z)=14zz = 2(y + x) = 2(-4z - 3z) = 2(-7z) = -14z
So z+14z=0    15z=0    z=0z + 14z = 0 \implies 15z = 0 \implies z = 0
So all numbers are zero.

Try with 1 white and 1 blue: a1a_1 (white), a2a_2 (blue).

a1=a2+a2=2a2a_1 = a_2 + a_2 = 2a_2
a2=2(a1+a1)=4a1a_2 = 2(a_1 + a_1) = 4a_1

So a1=2a2a_1 = 2a_2, a2=4a1a_2 = 4a_1
So a1=24a1=8a1    a1=0a_1 = 2 \cdot 4a_1 = 8a_1 \implies a_1 = 0

So all numbers are zero.

Try with 1 white and 1 red: a1a_1 (white), a2a_2 (red).

a1=a2+a2=2a2a_1 = a_2 + a_2 = 2a_2
a2=12(a1+a1)=a1a_2 = \frac{1}{2}(a_1 + a_1) = a_1
So a1=2a2=2a1    a1=0a_1 = 2a_2 = 2a_1 \implies a_1 = 0

So all numbers are zero.

Try with 1 white, 1 blue, 1 red: a1a_1 (white), a2a_2 (blue), a3a_3 (red).

a1=a3+a2a_1 = a_3 + a_2
a2=2(a1+a3)a_2 = 2(a_1 + a_3)
a3=12(a2+a1)a_3 = \frac{1}{2}(a_2 + a_1)

Let a1=xa_1 = x, a2=ya_2 = y, a3=za_3 = z.

x=y+zx = y + z
y=2(x+z)y = 2(x + z)
z=12(y+x)z = \frac{1}{2}(y + x)

From x=y+zx = y + z, y=xzy = x - z.

Plug into y=2(x+z)y = 2(x + z):
xz=2(x+z)x - z = 2(x + z)
xz=2x+2zx - z = 2x + 2z
xz2x2z=0x - z - 2x - 2z = 0
x3z=0-x - 3z = 0
x=3zx = -3z

So y=xz=3zz=4zy = x - z = -3z - z = -4z

Now z=12(y+x)=12(4z3z)=12(7z)=72zz = \frac{1}{2}(y + x) = \frac{1}{2}(-4z - 3z) = \frac{1}{2}(-7z) = -\frac{7}{2}z
So z+72z=0    92z=0    z=0z + \frac{7}{2}z = 0 \implies \frac{9}{2}z = 0 \implies z = 0

So all numbers are zero.

Therefore, the only possible way is that all numbers are zero unless all numbers are of the same color.

Suppose all numbers are white: ai=ai1+ai+1a_i = a_{i-1} + a_{i+1}, so aiai1ai+1=0a_i - a_{i-1} - a_{i+1} = 0 for all ii.
But the only solution is ai=0a_i = 0 for all ii.

Suppose all numbers are blue: ai=2(ai1+ai+1)a_i = 2(a_{i-1} + a_{i+1}), so ai2ai12ai+1=0a_i - 2a_{i-1} - 2a_{i+1} = 0 for all ii.
Again, only zero solution.

Suppose all numbers are red: ai=12(ai1+ai+1)a_i = \frac{1}{2}(a_{i-1} + a_{i+1}), so ai12ai112ai+1=0a_i - \frac{1}{2}a_{i-1} - \frac{1}{2}a_{i+1} = 0 for all ii.
Again, only zero solution.

Therefore, the only possible way is that w=0w = 0 or b=0b = 0, unless the circle is degenerate.

But the problem says w0w \neq 0, b0b \neq 0.

Therefore, the only possible ratio is 2\boxed{-2}.

(Alternatively, the only possible ratio is 2-2.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.