Maths Olympiad Prep

Library / /150 of 155

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Saudi Arabia

Given four numbers x,y,z,tx, y, z, t, let (a,b,c,d)(a, b, c, d) be a permutation of (x,y,z,t)(x, y, z, t) and set x1=abx_{1}=|a-b|, y1=bcy_{1}=|b-c|, z1=cdz_{1}=|c-d|, and t1=dat_{1}=|d-a|. From x1,y1,z1,t1x_{1}, y_{1}, z_{1}, t_{1}, form in the same fashion the numbers x2,y2,z2,t2x_{2}, y_{2}, z_{2}, t_{2}, and so on. It is known that xn=xx_{n}=x, yn=yy_{n}=y, zn=zz_{n}=z, tn=tt_{n}=t for some nn.
Find all possible values of (x,y,z,t)(x, y, z, t).

Solution

First, consider 4 sequences (xn),(yn),(zn),(tn)\left(x_{n}\right),\left(y_{n}\right),\left(z_{n}\right),\left(t_{n}\right) with x1=abx_{1}=|a-b|, y1=bcy_{1}=|b-c|, z1=cdz_{1}=|c-d|, t1=dat_{1}=|d-a|, (a,b,c,d)(a, b, c, d) is permutation of (x,y,z,t)(x, y, z, t). And
{xn+1=anbnyn+1=bncnzn+1=cndntn+1=dnan \left\{ \begin{array}{l} x_{n+1}=\left|a_{n}-b_{n}\right| \\ y_{n+1}=\left|b_{n}-c_{n}\right| \\ z_{n+1}=\left|c_{n}-d_{n}\right| \\ t_{n+1}=\left|d_{n}-a_{n}\right| \end{array} \right.
with (an,bn,cn,dn)(a_{n}, b_{n}, c_{n}, d_{n}) is a permutation of (xn,yn,zn,tn)(x_{n}, y_{n}, z_{n}, t_{n}).
From this, it is easy to see that xn,yn,zn,tn0x_{n}, y_{n}, z_{n}, t_{n} \geq 0 for all nn.
Let wn=max{xn,yn,zn,tn},n1w_{n}=\max \left\{x_{n}, y_{n}, z_{n}, t_{n}\right\}, n \geq 1. We have
wn=max{xn+1,yn+1,zn+1,tn+1}=max{anbn,bncn,cndn,dnan}max{an,bn,cn,dn}=max{xn,yn,zn,tn}=wn \begin{aligned} w_{n} & =\max \left\{x_{n+1}, y_{n+1}, z_{n+1}, t_{n+1}\right\} \\ & =\max \left\{\left|a_{n}-b_{n}\right|,\left|b_{n}-c_{n}\right|,\left|c_{n}-d_{n}\right|,\left|d_{n}-a_{n}\right|\right\} \\ & \leq \max \left\{a_{n}, b_{n}, c_{n}, d_{n}\right\}=\max \left\{x_{n}, y_{n}, z_{n}, t_{n}\right\}=w_{n} \end{aligned}
The equality occurs when there is at least one number among an,bn,cn,dna_{n}, b_{n}, c_{n}, d_{n} is equal to 00.
Hence the sequence (wn)(w_{n}) is non-increasing. Suppose that kk is a positive integer such that (xk,yk,zk,tk)=(x,y,z,t)(x_{k}, y_{k}, z_{k}, t_{k})=(x, y, z, t), then w1w2wk=w1w_{1} \geq w_{2} \geq \cdots \geq w_{k}=w_{1} which implies that w1=w2==wkw_{1}=w_{2}=\cdots=w_{k}. So there is at least one number among (x,y,z,t)(x, y, z, t) equal to 00. Based on the definition of the sequences, we can see that for each i=1,2,3,,ki=1,2,3, \ldots, k, the tuple (xi,yi,zi,ti)(x_{i}, y_{i}, z_{i}, t_{i}) has some common properties as follows:
1. There is at least one number that is 00.
2. There are two numbers equal.
3. In the permutation to obtain the next term, two equal numbers must be adjacent.
It is easy to check that 3 tuples as follows satisfy the given conditions:

i. If (x,y,z,t)=(0,0,0,0)(x, y, z, t)=(0,0,0,0).
ii. If (x,y,z,t)=(a,a,0,0)(x, y, z, t)=(a, a, 0,0) with a>0a>0 and its permutation.
iii. If (x,y,z,t)=(2a,a,a,0)(x, y, z, t)=(2a, a, a, 0) with a>0a>0 and its permutation.

Indeed, when (x,y,z,t)(x, y, z, t) is one of the 3 above tuples, then the form of tuple (xn,yn,zn,tn)\left(x_{n}, y_{n}, z_{n}, t_{n}\right) will not change. Continue, we will prove that if (x,y,z,t)(x, y, z, t) is a tuple that satisfies the condition, then it must be one of the 3 above forms. (*)

Without loss of generality, we may assume that xyzt=0,x>0x \geq y \geq z \geq t=0, x>0. Since there are two numbers equal among 4 numbers, we consider some cases:

1. If x=yx=y then we have (x,y,z,t)=(a,a,b,0)(x, y, z, t)=(a, a, b, 0) with ab0,a>0a \geq b \geq 0, a>0. Based on the 3rd property, (x1,y1,z1,t1)\left(x_{1}, y_{1}, z_{1}, t_{1}\right) can only be (0,ab,b,a)(0, a-b, b, a). Apply the 2nd property, we have:
- If a=ab,b=0a=a-b, b=0, we have (x,y,z,t)=(a,a,0,0)(x, y, z, t)=(a, a, 0,0), which satisfies the given condition.
- If a=b,ab=0a=b, a-b=0, then we have (x,y,z,t)=(a,a,a,0)(x, y, z, t)=(a, a, a, 0) with a>0a>0. So (x1,y1,z1,t1)\left(x_{1}, y_{1}, z_{1}, t_{1}\right) will be (0,0,a,a)(0,0, a, a). But from this, the form will not change, so we cannot obtain the original form anymore. This case doesn't satisfy.
- If ab=ba-b=b then a=2ba=2b, we have (x,y,z,t)=(2b,2b,b,0)(x, y, z, t)=(2b, 2b, b, 0) and (x1,y1,z1,t1)=(0,b,b,2b)\left(x_{1}, y_{1}, z_{1}, t_{1}\right)=(0, b, b, 2b). But the form of this tuple will not change and similarly, this case doesn't satisfy.

2. If y=zy=z, then we have (x,y,z,t)=(a,b,b,0)(x, y, z, t)=(a, b, b, 0) with ab>0a \geq b>0. So (x1,y1,z1,t1)(x_{1}, y_{1}, z_{1}, t_{1}) can be (ab,0,b,a)(a-b, 0, b, a). Apply the 2nd property, we have:
- If ab=0,a=ba-b=0, a=b, we have (x,y,z,t)=(a,a,a,0)(x, y, z, t)=(a, a, a, 0), not satisfy.
- If ab=a,b=0a-b=a, b=0, we have the tuple (x,y,z,t)=(a,0,0,0)(x, y, z, t)=(a, 0,0,0) and (x1,y1,z1,t1)=(a,0,0,a)\left(x_{1}, y_{1}, z_{1}, t_{1}\right)=(a, 0,0, a). It is easy to see that this case doesn't satisfy.
- If ab=ba-b=b, we have (x,y,z,t)=(2b,b,b,0)(x, y, z, t)=(2b, b, b, 0) which satisfies.

3. If z=0z=0 then we have (x,y,z,t)=(a,b,0,0)(x, y, z, t)=(a, b, 0,0) with ab0a \geq b \geq 0. So (x1,y1,z1,t1)(x_{1}, y_{1}, z_{1}, t_{1}) can be (ab,0,b,a)(a-b, 0, b, a). Apply the 2nd property, we have:
- If ab=0,a=ba-b=0, a=b, we have (x,y,z,t)=(a,a,0,0)(x, y, z, t)=(a, a, 0,0), satisfies.
- If ab=a,b=0a-b=a, b=0, we have (x,y,z,t)=(a,0,0,0)(x, y, z, t)=(a, 0,0,0), not satisfy.
- If ab=ba-b=b, we have the tuple (x,y,z,t)=(2b,b,0,0)(x, y, z, t)=(2b, b, 0,0) and (x1,y1,z1,t1)=(b,b,0,2b)\left(x_{1}, y_{1}, z_{1}, t_{1}\right)=(b, b, 0,2b). It is easy to see that this case doesn't satisfy.

Therefore, there are 3 tuples that satisfy the given condition as above.

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 and solution reproduced as published; topic and difficulty added by this site.