Maths Olympiad Prep

Library / /6 of 6

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Brazil

Let XX be the set of all sequences a=(a1,a2,,a2000)a = (a_1, a_2, \dots, a_{2000}) such that ai{0,1,2}a_i \in \{0, 1, 2\} for 1i10001 \le i \le 1000 and ai{0,1}a_i \in \{0, 1\} for 1001i20001001 \le i \le 2000. Given a,ba, b in XX, we define the distance d(a,b)d(a, b) between aa and bb as the number of values for ii, 1i20001 \le i \le 2000, for which aibia_i \ne b_i. Find the number of distance-preserving functions f:XXf: X \to X, i.e., such that d(f(a),f(b))=d(a,b)d(f(a), f(b)) = d(a, b) for all aa and bb in XX.

Solution

Let a=f(0,0,0,,0)a = f(0, 0, 0, \dots, 0), b=f(1,0,0,,0)b = f(1, 0, 0, \dots, 0) and c=f(2,0,0,,0)c = f(2, 0, 0, \dots, 0), say a=(a1,a2,,a2000)a = (a_1, a_2, \dots, a_{2000}), b=(b1,b2,,b2000)b = (b_1, b_2, \dots, b_{2000}) and c=(c1,c2,,c2000)c = (c_1, c_2, \dots, c_{2000}). It's easy to conclude that there exists a unique 1i020001 \le i_0 \le 2000 such that a,ba, b and cc differ at position i0i_0, i.e., ai0bi0ci0ai0a_{i_0} \ne b_{i_0} \ne c_{i_0} \ne a_{i_0}. This also gives i01000i_0 \le 1000. Another easy argument shows that if x0=f(0,d2,d3,,d2000)=(x1,x2,,x2000)x_0 = f(0, d_2, d_3, \dots, d_{2000}) = (x_1, x_2, \dots, x_{2000}), then xi0=ai0x_{i_0} = a_{i_0} and also if x1=f(1,e2,e3,,e2000)=(y1,y2,,y2000)x_1 = f(1, e_2, e_3, \dots, e_{2000}) = (y_1, y_2, \dots, y_{2000}), then yi0=bi0y_{i_0} = b_{i_0}.
A similar argument shows the following: let
at=f(0,0,,0,,0)=(a1,a2,,a2000), a_t = f(0, 0, \dots, 0, \dots, 0) = (a_1, a_2, \dots, a_{2000}),
bt=f(0,0,,1,,0)=(b1,b2,,b2000), b_t = f(0, 0, \dots, 1, \dots, 0) = (b_1, b_2, \dots, b_{2000}),
ct=f(0,0,,2,,0)=(c1,c2,,c2000), c_t = f(0, 0, \dots, 2, \dots, 0) = (c_1, c_2, \dots, c_{2000}),
where t1000t \le 1000 is the position of 1 and 2, and x=f(x1,x2,,x2000)=(y1,y2,,y2000)x = f(x_1, x_2, \dots, x_{2000}) = (y_1, y_2, \dots, y_{2000}). Therefore yit=aity_{i_t} = a_{i_t} if xt=0x_t = 0 (iti_t is the position that changes from ata_t to btb_t), yit=bity_{i_t} = b_{i_t} if xt=1x_t = 1 and yit=city_{i_t} = c_{i_t} if xt=2x_t = 2.
Now, it's clear that (i1,i2,,i1000)(i_1, i_2, \dots, i_{1000}) is a permutation of (1,2,,1000)(1, 2, \dots, 1000). On the other hand, if at=f(0,0,,0,,0)=(a1,a2,,a2000)a_t = f(0, 0, \dots, 0, \dots, 0) = (a_1, a_2, \dots, a_{2000}) and bt=f(0,0,,1,,0)=(b1,b2,,b2000)b_t = f(0, 0, \dots, 1, \dots, 0) = (b_1, b_2, \dots, b_{2000}), where t1000t \ge 1000 is the position of 1, there is a unique j1000j \ge 1000 such that ajbja_j \ne b_j. Denoting this jj by iji_j, if x=f(x1,x2,,x2000)=(y1,y2,,y2000)x = f(x_1, x_2, \dots, x_{2000}) = (y_1, y_2, \dots, y_{2000}), one can show in a similar way that yit=aity_{i_t} = a_{i_t} if xt=0x_t = 0 and yit=bity_{i_t} = b_{i_t} if xt=1x_t = 1. Finally, in order to count the number of different functions f:XXf: X \to X, it suffices to choose (i1,i2,,i1000)(i_1, i_2, \dots, i_{1000}), which is a permutation of (1,2,,1000)(1, 2, \dots, 1000), (i1001,i1002,,i2000)(i_{1001}, i_{1002}, \dots, i_{2000}), which is a permutation of (1001,1002,,2000)(1001, 1002, \dots, 2000), and (ait,bit,cit)(a_{i_t}, b_{i_t}, c_{i_t}) for 1t10001 \le t \le 1000 and (ait,bit)(a_{i_t}, b_{i_t}) for 1001t20001001 \le t \le 2000.
This gives that the total number of functions is 1000!2×1210001000!^2 \times 12^{1000}.

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.