Maths Olympiad Prep

Library / /112 of 133

, 2015

Combinatorics Difficulty 6.7 National olympiad Prove it Saudi Arabia

Find the number of 6-tuples (a1,a2,a3,a4,a5,a6)(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}) of distinct positive integers satisfying the following two conditions:

a. a1+a2+a3+a4+a5+a6=30a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} = 30;

b. We can write a1,a2,a3,a4,a5,a6a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6} on sides of a hexagon such that after a finite number of times choosing a vertex of the hexagon and adding 1 to the two numbers written on two sides adjacent to the vertex, we obtain a hexagon with equal numbers on its sides.

Solution

We label the vertex of the hexagon by 1,2,3,4,5,61,2,3,4,5,6 and suppose that six numbers are written in the order a,b,c,d,e,fa, b, c, d, e, f on the edges (1,2),(2,3),,(6,1)(1,2), (2,3), \ldots, (6,1), respectively.

We first notice that by choosing a vertex of the hexagon and adding 1 to the two numbers written on two adjacent sides to the vertex, the difference (a+c+e)(b+d+f)(a + c + e) - (b + d + f) is an invariant. Thus, if we want to obtain a hexagon with equal numbers on its sides, we must have a+c+e=b+d+fa + c + e = b + d + f at the beginning.

We will show that it is also sufficient. Let NN be a big integer, for example, we can take N>30N > 30. We choose the vertices 1,2,4,51,2,4,5 and add 1 to the two numbers written on two sides of those vertices by Nf,Nb,NcN - f, N - b, N - c and NeN - e times, respectively. Then, we obtain a hexagon with six numbers

a+2Nbf,N,N,d+2Nec,N,Na + 2N - b - f, N, N, d + 2N - e - c, N, N.

Since a+c+e=b+d+fa + c + e = b + d + f, we have a+2Nbf=d+2Nec=M>Na + 2N - b - f = d + 2N - e - c = M > N (since N>30=a+b+c+d+e+fN > 30 = a + b + c + d + e + f). We now can choose the vertices 3, 6 for MNM - N times each, then we obtain a hexagon with numbers MM on all of its sides.

Now, we count how many 6-tuples (a,b,c,d,e,f)(a, b, c, d, e, f) of distinct positive integers with a+c+e=b+d+f=15a + c + e = b + d + f = 15.

We list all triples of distinct positive integers with sum 15: (1,2,12),(1,3,11),(1,4,10),(1,5,9),(1,6,8),(2,3,10),(2,4,9),(2,5,8),(2,6,7),(3,4,8),(3,5,7),(4,5,6)(1,2,12), (1,3,11), (1,4,10), (1,5,9), (1,6,8), (2,3,10), (2,4,9), (2,5,8), (2,6,7), (3,4,8), (3,5,7), (4,5,6). We then check that there are exactly 19 times we can pair these triples to obtain 6 distinct numbers.

Since we can permute the numbers on each tuple, the total number of 6-tuples satisfying the given conditions is 19×6!19 \times 6!.

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.