Maths Olympiad Prep

Library / /430 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

Let nn be a positive integer relatively prime to 6. We paint the vertices of a regular nn-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours. C4\mathbf{C 4}. Find all positive integers nn for which we can fill in the entries of an n×nn \times n table with the following properties:
- each entry can be one of I,MI, M and OO;
- in each row and each column, the letters I,MI, M and OO occur the same number of times; and
- in any diagonal whose number of entries is a multiple of three, the letters I,MI, M and OO occur the same number of times.

Solution

For k=1,2,3k=1,2,3, let aka_{k} be the number of isosceles triangles whose vertices contain exactly kk colours. Suppose on the contrary that a3=0a_{3}=0. Let b,c,db, c, d be the number of vertices of the three different colours respectively. We now count the number of pairs (,E)(\triangle, E) where \triangle is an isosceles triangle and EE is a side of \triangle whose endpoints are of different colours. On the one hand, since we have assumed a3=0a_{3}=0, each triangle in the pair must contain exactly two colours, and hence each triangle contributes twice. Thus the number of pairs is 2a22 a_{2}. On the other hand, if we pick any two vertices A,BA, B of distinct colours, then there are three isosceles triangles having these as vertices, two when ABA B is not the base and one when ABA B is the base since nn is odd. Note that the three triangles are all distinct as (n,3)=1(n, 3)=1. In this way, we count the number of pairs to be 3(bc+cd+db)3(b c+c d+d b). However, note that 2a22 a_{2} is even while 3(bc+cd+db)3(b c+c d+d b) is odd, as each of b,c,db, c, d is. This yields a contradiction and hence a31a_{3} \geqslant 1. Comment. A slightly stronger version of this problem is to replace the condition (n,6)=1(n, 6)=1 by nn being odd (where equilateral triangles are regarded as isosceles triangles). In that case, the only difference in the proof is that by fixing any two vertices A,BA, B, one can find exactly one or three isosceles triangles having these as vertices. But since only parity is concerned in the solution, the proof goes the same way. The condition that there is an odd number of vertices of each colour is necessary, as can be seen from the following example. Consider n=25n=25 and we label the vertices A0,A1,,A24A_{0}, A_{1}, \ldots, A_{24}. Suppose colour 1 is used for A0A_{0}, colour 2 is used for A5,A10,A15,A20A_{5}, A_{10}, A_{15}, A_{20}, while colour 3 is used for the remaining vertices. Then any isosceles triangle having colours 1 and 2 must contain A0A_{0} and one of A5,A10,A15,A20A_{5}, A_{10}, A_{15}, A_{20}. Clearly, the third vertex must have index which is a multiple of 5 so it is not of colour 3.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.