For each positive integer n, let Sn={0,1,2,…,2n+1}. Consider the function f:(Z×Sn)→[0;1] satisfying the following conditions:
i/ f(x,0)=f(x,2n+1)=0 for all x from integers.
ii/ f(x−1,y)+f(x+1,y)+f(x,y−1)+f(x,y+1)=1 for all x,y∈Z and 1≤y≤2n.
Let F be the set of all such functions.
1. Prove that ∣F∣ is infinite. 2. For each function f∈F, let vf be the image set of f. Prove that ∣vf∣ is finite. 3. Find the maximum value of ∣vf∣ where f∈F.
Solution
1. In equation ii/ we see that (x−1)−y≡(x+1)−y≡x−(y−1)≡x−(y+1)(mod2) That is, the values of f(x,y) where x,y have the same parity and the values of f(x,y) where x,y have the opposite parity have no connection. We will find the way to define function f in both cases. In the coordinate plane Oxy, we consider the lattice points (i,j) where i,j are integers and 0≤j≤2n+1. The point (i,j) is assigned with the value 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].
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, the sum of all assigned numbers is equal to 1. For each lattice point A(i,j), let f1(A)=f(i+2,j), f2(A)=f(i−2,j). Let ak=f(k,k) where k=1,2,3,…,2n be the value assigned to Ak(k,k). By the condition, we have a1+a2+f1(A1)+0a2+a3+f1(A2)+f1(A1)…=1=1⇒f1(A1)⇒f1(A2)=1−a1−a2,=a1−a3, a2n−1+a2n+f1(A2n−2)+f1(A2n−1)a2n+0+f1(A2n−1)+f1(A2n)=1=1⇒f1(A2n−1)⇒f1(A2n)=a1−a2n,=a1 Similarly, we have f2(A2n)f2(A2n−1)…=1−a2n−1−a2n=a2n−a2n−2 f2(A1)f2(A2)=1−a1−a2n,=a2n From that we see that if the sequence ak is given then the values of f1(Ak),f2(Ak) are defined. We will choose ak such that f1(Ak),f2(Ak) belong to [0;1]. We choose a1≥a3≥a5≥⋯≥a2n−1,a2≤a4≤a6≤⋯≤a2n,a1+a2n≤1 then f1(Ak),f2(Ak)∈[0;1]. Moreover, we see that f1(A1)f2(A1)≥f1(A3)≥⋯≥f1(A2n−1),f1(A2)≤f1(A4)≤⋯≤f1(A2n),f1(A1)+f1(A2n)≤1,≥f2(A3)≥⋯≥f2(A2n−1),f2(A2)≤f2(A4)≤⋯≤f2(A2n),f2(A1)+f2(A2n)≤1 So, the monotonicity of two subsequences of odd indices and even indices still holds for f1(Ak) and f2(Ak), as well as the last condition. Thus, similarly, from the sequence f1(Ak), we can find f1(f1(Ak)), and from f2(Ak), we can find f2(f2(Ak)) and so on, and we can find all values of f(x,y) where x−y is even.
By denoting bk=f(k+1,k) the values assigned to Bk(k+1,k), where k=1,2,3,…,2n then by similar way as below, we can construct all values of f(x,y) where x−y is odd. It is easy to see that there are infinitely many ways to choose sequences (ak),(bk) which satisfy the following condition. Thus there exists infinitely many functions with the given properties, i.e. ∣F∣ is infinite. (Q.E.D)
2. In the equation f(x−1,y)+f(x+1,y)+f(x,y−1)+f(x,y+1)=1, replacing x,y by x+1,y+1, we get f(x,y+1)+f(x+2,y+1)+f(x+1,y)+f(x+1,y+2)=1. Therefore 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(3,1)+f(4,0)=f(5,3)+f(6,2)=⋯=f(2n+3,2n+1)+f(2n+4,2n). Thus f(1,1)=f(2n+2,2n), f(3,1)=f(2n+4,2n). Similarly, we have f(2,2)=f(2n+2,2n−1), f(4,2)=f(2n+5,2n−1). Repeatedly apply (*), we have 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+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+1−k)=f(4n+2+k,k) for all k=1,2,3,…,2n. And therefore, by induction, we get f(k,k)=f((2n+1)i+k,2n+1−k)=f((4n+2)i+k,k) where i∈Z and k=1,2,3,…,2n. Moreover, the definition of values in the next diagonal (to the right) is the same in the diagonals (k,k) and ((2n+1)i+k,2n+1−k) so the values at respective points are equal. Therefore values of f are repeated as illustrated in the picture, i.e. the values of f(x,y) with x−y even repeat the values assigned to the lattice points inside triangle Ω with vertices at (1,1),(2n+1,2n),(4n+1,1). Number of such values is finite and we can compute that there are at most 1+2+3+…+2n=n(2n+1) distinct values. Similarly with the values of f(x,y) where x−y is odd, in this case we also have at most n(2n+1) distinct values. Besides that, we have 0 as one value of f(x,y). Summing all above arguments, we have ∣vf∣≤2n(2n+1)+1. Thus, ∣vf∣ is finite for all f∈F, and we have done.
3. We will construct a function f for which ∣vf∣=2n(2n+1)+1 and show that this is the maximum value of ∣vf∣. By induction, we can prove that f(i+2k,i)=4(1−(−1)i)(1−(−1)k)+(−1)kak+i−(−1)k+iak for all i=1,2,…,2n and k∈Z such that 0≤k+i≤2n+1. (**) Indeed, for k=0 then () is obviously true. Assume that () is true for all (i,k) with k≤m and k=m+1,i≤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. By the induction hypothesis, we can compute f(j+1+2(m+1),j+1)=4(1−(−1)j+1)(1−(−1)m+1)+(−1)m+1am+j+2−(−1)m+j+2am+1. Therefore (**) is true for i=j+1,k=m+1. Thus, the values assigned to the points inside the triangle Ω have the form δij±ai±aj with δij∈{0,1}, where δij as well as the signs of ai,aj are well defined by i,j. Next, we choose a2k−1=32k−11,a2k=32(n+1−k)1 where k=1,2,…,n then using the fact that every integer can be expressed in the form ∑i=0rδi3i where δi=0 and ei∈{−1,0,1} in only one way, we see that all values f(x,y) assigned to the points inside triangle Ω are distinct and are non-zero, i.e. we have exactly n(2n+1) such values. We have constructed the values of f(x,y) where x−y is even. Similarly, for construction of f(x,y) where x−y is odd, we choose b2k−1=32k−131,b2k=32(n+1−k)31 where k=1,2,…,2n. then the values of the form δij′±bi±bj are also non-zero, distinct and different from the values δij±ai±aj. From which, we construct all values for f(x,y) and we have at all 2n(2n+1)+1 distinct values. Thus, the maximum value of ∣vf∣ on F is 2n(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.