Maths Olympiad Prep

Library / /195 of 196

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Soviet Union

Problem:

a. Given a quadruple (a,b,c,d)(a, b, c, d) of positive reals, transform to the new quadruple (ab,bc,cd,da)(ab, bc, cd, da). Repeat arbitrarily many times. Prove that you can never return to the original quadruple unless a=b=c=d=1a = b = c = d = 1.

b. Given nn a power of 22, and an nn-tuple (a1,a2,,an)(a_1, a_2, \ldots, a_n) transform to a new nn-tuple (a1a2,a2a3,,an1an,ana1)(a_1 a_2, a_2 a_3, \ldots, a_{n-1} a_n, a_n a_1). If all the members of the original nn-tuple are 11 or 1-1, prove that with sufficiently many repetitions you obtain all 11s.

Solution

Solution:

a.
Let Q0Q_0 be the original quadruple (a,b,c,d)(a, b, c, d) and QnQ_n the quadruple after nn transformations. If abcd>1abcd > 1, then the products form a strictly increasing sequence, so return is impossible. Similarly if abcd<1abcd < 1. So we must have abcd=1abcd = 1. Let the largest of the four values of a quadruple QQ be M(Q)M(Q). If a member of Q1Q_1 is not 11, then M(Q1)>1M(Q_1) > 1. Q3Q_3 consists of the elements of Q1Q_1 squared and permuted, so M(Q3)=M(Q1)2M(Q_3) = M(Q_1)^2. Hence the sequence M(Q1)M(Q_1), M(Q3)M(Q_3), M(Q5)M(Q_5), ... increases without limit. This means no return is possible, because a return would lead to the values cycling.

b.
After r<nr < n transformations, the first number of the nn-tuple is the product a1((r0))a2((r1))ar+1((rr))a_1^{(r\choose 0)} a_2^{(r\choose 1)} \ldots a_{r+1}^{(r\choose r)}, where ((ri))(r\choose i) denotes the binomial coefficient. [This is an easy induction.] Hence after n=2kn = 2^k transformations it is a12a_1^2 times the product a2((n1))an((n1))a_2^{(n\choose 1)} \ldots a_n^{(n\choose 1)}. So it is sufficient to prove that ((ni))(n\choose i) is even for nn a power of 22 and 0<i<n0 < i < n. But observe that (n i) = (n-1 i) n/(n-i)\text{(n i) = (n-1 i) n/(n-i)} and nn is divisible by a higher power of 22 than nin-i.

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.