Maths Olympiad Prep

Library / /16 of 18

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Vietnam

For each positive integer nn, let Sn={0,1,2,,2n+1}S_n = \{0,1,2,\ldots,2n+1\}. Consider the function f:(Z×Sn)[0;1]f : (\mathbb{Z} \times S_n) \to [0;1] satisfying the following conditions:

i/ f(x,0)=f(x,2n+1)=0f(x,0) = f(x,2n+1) = 0 for all xx from integers.

ii/ f(x1,y)+f(x+1,y)+f(x,y1)+f(x,y+1)=1f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)=1 for all x,yZx,y \in \mathbb{Z} and 1y2n1 \le y \le 2n.

Let FF be the set of all such functions.

1. Prove that F|F| is infinite.
2. For each function fFf \in F, let vfv_f be the image set of ff. Prove that vf|v_f| is finite.
3. Find the maximum value of vf|v_f| where fFf \in F.

Solution

1. In equation ii/ we see that
(x1)y(x+1)yx(y1)x(y+1)(mod2) (x-1)-y \equiv (x+1)-y \equiv x-(y-1) \equiv x-(y+1) \pmod{2}
That is, the values of f(x,y)f(x,y) where x,yx,y have the same parity and the values of f(x,y)f(x,y) where x,yx,y have the opposite parity have no connection.
We will find the way to define function ff in both cases.
In the coordinate plane OxyOxy, we consider the lattice points (i,j)(i, j) where i,ji, j are integers and 0j2n+10 \le j \le 2n+1. The point (i,j)(i, j) is assigned with the value f(i,j)f(i, j).
The condition i/ gives us that all numbers in the border (upper and lower) are 0; and all inner points are assigned with the numbers from [0;1][0; 1].

The condition ii/ means for each small skew square (with diagonal parallel to the axis), with vertices in the lattice points and with side 2\sqrt{2}, the sum of all assigned numbers is equal to 1.
For each lattice point A(i,j)A(i, j), let f1(A)=f(i+2,j)f_1(A) = f(i+2,j), f2(A)=f(i2,j)f_2(A) = f(i-2,j).
Let ak=f(k,k)a_k = f(k, k) where k=1,2,3,,2nk=1,2,3,\ldots,2n be the value assigned to Ak(k,k)A_k(k, k). By the condition, we have
a1+a2+f1(A1)+0=1f1(A1)=1a1a2,a2+a3+f1(A2)+f1(A1)=1f1(A2)=a1a3, \begin{align*} a_1 + a_2 + f_1(A_1) + 0 &= 1 & \Rightarrow f_1(A_1) &= 1 - a_1 - a_2, \\ a_2 + a_3 + f_1(A_2) + f_1(A_1) &= 1 & \Rightarrow f_1(A_2) &= a_1 - a_3, \\ \dots & & \end{align*}
a2n1+a2n+f1(A2n2)+f1(A2n1)=1f1(A2n1)=a1a2n,a2n+0+f1(A2n1)+f1(A2n)=1f1(A2n)=a1 \begin{align*} a_{2n-1} + a_{2n} + f_1(A_{2n-2}) + f_1(A_{2n-1}) &= 1 & \Rightarrow f_1(A_{2n-1}) &= a_1 - a_{2n}, \\ a_{2n} + 0 + f_1(A_{2n-1}) + f_1(A_{2n}) &= 1 & \Rightarrow f_1(A_{2n}) &= a_1 \end{align*}
Similarly, we have
f2(A2n)=1a2n1a2nf2(A2n1)=a2na2n2 \begin{align*} f_2(A_{2n}) &= 1 - a_{2n-1} - a_{2n} \\ f_2(A_{2n-1}) &= a_{2n} - a_{2n-2} \\ \dots & \end{align*}
f2(A1)=1a1a2n,f2(A2)=a2n \begin{align*} f_2(A_1) &= 1 - a_1 - a_{2n}, \\ f_2(A_2) &= a_{2n} \end{align*}
From that we see that if the sequence aka_k is given then the values of f1(Ak),f2(Ak)f_1(A_k), f_2(A_k) are defined. We will choose aka_k such that f1(Ak),f2(Ak)f_1(A_k), f_2(A_k) belong to [0;1][0;1].
We choose a1a3a5a2n1,a2a4a6a2n,a1+a2n1a_1 \ge a_3 \ge a_5 \ge \dots \ge a_{2n-1}, a_2 \le a_4 \le a_6 \le \dots \le a_{2n}, a_1 + a_{2n} \le 1 then f1(Ak),f2(Ak)[0;1]f_1(A_k), f_2(A_k) \in [0;1].
Moreover, we see that
f1(A1)f1(A3)f1(A2n1),f1(A2)f1(A4)f1(A2n),f1(A1)+f1(A2n)1,f2(A1)f2(A3)f2(A2n1),f2(A2)f2(A4)f2(A2n),f2(A1)+f2(A2n)1 \begin{align*} f_1(A_1) &\ge f_1(A_3) \ge \dots \ge f_1(A_{2n-1}), f_1(A_2) \le f_1(A_4) \le \dots \le f_1(A_{2n}), f_1(A_1) + f_1(A_{2n}) \le 1, \\ f_2(A_1) &\ge f_2(A_3) \ge \dots \ge f_2(A_{2n-1}), f_2(A_2) \le f_2(A_4) \le \dots \le f_2(A_{2n}), f_2(A_1) + f_2(A_{2n}) \le 1 \end{align*}
So, the monotonicity of two subsequences of odd indices and even indices still holds for f1(Ak)f_1(A_k) and f2(Ak)f_2(A_k), as well as the last condition.
Thus, similarly, from the sequence f1(Ak)f_1(A_k), we can find f1(f1(Ak))f_1(f_1(A_k)), and from f2(Ak)f_2(A_k), we can find f2(f2(Ak))f_2(f_2(A_k)) and so on, and we can find all values of f(x,y)f(x,y) where xyx-y is even.

Figure 1
By denoting bk=f(k+1,k)b_k = f(k+1, k) the values assigned to Bk(k+1,k)B_k(k+1, k), where k=1,2,3,,2nk=1,2,3,\ldots,2n then by similar way as below, we can construct all values of f(x,y)f(x,y) where xyx-y is odd.
It is easy to see that there are infinitely many ways to choose sequences (ak),(bk)(a_k), (b_k) which satisfy the following condition. Thus there exists infinitely many functions with the given properties, i.e. F|F| is infinite. (Q.E.D)

2. In the equation f(x1,y)+f(x+1,y)+f(x,y1)+f(x,y+1)=1f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)=1, replacing x,yx,y by x+1,y+1x+1,y+1, we get f(x,y+1)+f(x+2,y+1)+f(x+1,y)+f(x+1,y+2)=1f(x,y+1)+f(x+2,y+1)+f(x+1,y)+f(x+1,y+2)=1.
Therefore f(x1,y)+f(x,y1)=f(x+1,y+2)+f(x+2,y+1)f(x-1,y)+f(x,y-1) = f(x+1,y+2)+f(x+2,y+1) (*) or
f(1,1)+f(2,0)=f(3,3)+f(4,2)==f(2n+1,2n+1)+f(2n+2,2n),f(1,1)+f(2,0) = f(3,3)+f(4,2) = \dots = f(2n+1,2n+1)+f(2n+2,2n),
f(3,1)+f(4,0)=f(5,3)+f(6,2)==f(2n+3,2n+1)+f(2n+4,2n).f(3,1)+f(4,0) = f(5,3)+f(6,2) = \dots = f(2n+3,2n+1)+f(2n+4,2n).
Thus f(1,1)=f(2n+2,2n)f(1,1) = f(2n+2,2n), f(3,1)=f(2n+4,2n)f(3,1) = f(2n+4,2n).
Similarly, we have f(2,2)=f(2n+2,2n1)f(2,2) = f(2n+2,2n-1), f(4,2)=f(2n+5,2n1)f(4,2) = f(2n+5,2n-1).
Repeatedly apply (*), we have
f(k,k)=f(2n+1+k,2n+1k),f(k+2,k)=f(2n+3+k,2n+1k). f(k,k) = f(2n+1+k, 2n+1-k), f(k+2,k) = f(2n+3+k, 2n+1-k).
Similarly, we have
f(2n+k,2n+1k)=f(4n+2+k,k),f(2n+3+k,2n+1k)=f(4n+4+k,k). f(2n+k, 2n+1-k) = f(4n+2+k, k), f(2n+3+k, 2n+1-k) = f(4n+4+k, k).
Thus, f(k,k)=f(2n+1+k,2n+1k)=f(4n+2+k,k)f(k,k) = f(2n+1+k, 2n+1-k) = f(4n+2+k, k) for all k=1,2,3,,2nk=1,2,3,\ldots,2n. And therefore, by induction, we get
f(k,k)=f((2n+1)i+k,2n+1k)=f((4n+2)i+k,k) where iZ and k=1,2,3,,2n. f(k,k) = f((2n+1)i+k, 2n+1-k) = f((4n+2)i+k, k) \text{ where } i \in \mathbb{Z} \text{ and } k=1,2,3,\ldots,2n.
Moreover, the definition of values in the next diagonal (to the right) is the same in the diagonals (k,k)(k,k) and ((2n+1)i+k,2n+1k)((2n+1)i+k, 2n+1-k) so the values at respective points are equal. Therefore values of ff are repeated as illustrated in the picture, i.e. the values of f(x,y)f(x,y) with xyx-y even repeat the values assigned to the lattice points inside triangle Ω\Omega with vertices at (1,1),(2n+1,2n),(4n+1,1)(1,1), (2n+1,2n), (4n+1,1).
Figure 2
Number of such values is finite and we can compute that there are at most
1+2+3++2n=n(2n+1) distinct values. 1+2+3+\ldots+2n = n(2n+1) \text{ distinct values.}
Similarly with the values of f(x,y)f(x,y) where xyx-y is odd, in this case we also have at most n(2n+1)n(2n+1) distinct values. Besides that, we have 0 as one value of f(x,y)f(x, y). Summing all above arguments, we have vf2n(2n+1)+1|v_f| \le 2n(2n+1)+1.
Thus, vf|v_f| is finite for all fFf \in F, and we have done.

3. We will construct a function ff for which vf=2n(2n+1)+1|v_f| = 2n(2n+1)+1 and show that this is the maximum value of vf|v_f|.
By induction, we can prove that
f(i+2k,i)=(1(1)i)(1(1)k)4+(1)kak+i(1)k+iak f(i+2k,i) = \frac{(1-(-1)^i)(1-(-1)^k)}{4} + (-1)^k a_{k+i} - (-1)^{k+i} a_k
for all i=1,2,,2ni=1,2,\ldots,2n and kZk \in \mathbb{Z} such that 0k+i2n+10 \le k+i \le 2n+1. (**)
Indeed, for k=0k=0 then () is obviously true.
Assume that (
) is true for all (i,k)(i,k) with kmk \le m and k=m+1,ijk=m+1, i \le j. From the condition ii/, we have
f(j+1+2(m+1),j+1)+f(j+1+2m,j+1)+f(j+2(m+1),j)+f(j+2+2m,j+2)=1. f(j+1+2(m+1), j+1)+f(j+1+2m, j+1)+f(j+2(m+1), j)+f(j+2+2m, j+2)=1.
By the induction hypothesis, we can compute
f(j+1+2(m+1),j+1)=(1(1)j+1)(1(1)m+1)4+(1)m+1am+j+2(1)m+j+2am+1. f(j+1+2(m+1), j+1) = \frac{(1-(-1)^{j+1})(1-(-1)^{m+1})}{4} + (-1)^{m+1}a_{m+j+2} - (-1)^{m+j+2}a_{m+1}.
Therefore (**) is true for i=j+1,k=m+1i = j+1, k = m+1.
Thus, the values assigned to the points inside the triangle Ω\Omega have the form δij±ai±aj\delta_{ij} \pm a_i \pm a_j with δij{0,1}\delta_{ij} \in \{0,1\}, where δij\delta_{ij} as well as the signs of ai,aja_i, a_j are well defined by i,ji, j.
Next, we choose a2k1=132k1,a2k=132(n+1k)a_{2k-1} = \frac{1}{3^{2k-1}}, a_{2k} = \frac{1}{3^{2(n+1-k)}} where k=1,2,,nk=1,2,\ldots,n then using the fact that every integer can be expressed in the form i=0rδi3i\sum_{i=0}^{r} \delta_i 3^i where δi0\delta_i \ne 0 and ei{1,0,1}e_i \in \{-1,0,1\} in only one way, we see that all values f(x,y)f(x,y) assigned to the points inside triangle Ω\Omega are distinct and are non-zero, i.e. we have exactly n(2n+1)n(2n+1) such values. We have constructed the values of f(x,y)f(x,y) where xyx-y is even.
Similarly, for construction of f(x,y)f(x,y) where xyx-y is odd, we choose
b2k1=132k13,b2k=132(n+1k)3 where k=1,2,,2n. b_{2k-1} = \frac{1}{3^{2k-1}\sqrt{3}}, b_{2k} = \frac{1}{3^{2(n+1-k)}\sqrt{3}} \text{ where } k=1,2,\ldots,2n.
then the values of the form δij±bi±bj\delta'_{ij} \pm b_i \pm b_j are also non-zero, distinct and different from the values δij±ai±aj\delta_{ij} \pm a_i \pm a_j.
From which, we construct all values for f(x,y)f(x,y) and we have at all 2n(2n+1)+12n(2n+1)+1 distinct values.
Thus, the maximum value of vf|v_f| on FF is 2n(2n+1)+12n(2n+1)+1.

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.