Maths Olympiad Prep

Library / /404 of 520

Combinatorics Difficulty 6.0 AIME, harder Prove it

Problem 4 Let nn be an integer with n3n \geq 3 and assume that 2n2 n vertices of a regular (4n+1)(4 n+1)-gon are coloured. Show that there must exist three of the coloured vertices forming an isosceles triangle.

Solution

Solution 1 a) Notice that {2019!12019!,2019!22019!,,2019!20192019!}\left\{2019!\cdot 1^{2019!}, 2019!\cdot 2^{2019!}, \ldots, 2019!\cdot 2019^{2019!}\right\} is such a set. Observe that if all the elements are divisible by 2019! then the arithmetic means will be integer for all the subsets. Also, if AA is a set such that the geometric means are integer for all non-empty subsets and the set BB is obtained from the set AA by multiplying each element with with a given integer cc then all the non-empty subsets of BB will have an integer geometric mean, since

cai1cai2caikk=cai1ai2aikk \sqrt[k]{c a_{i_{1}} c a_{i_{2}} \cdots c a_{i_{k}}}=c \sqrt[k]{a_{i_{1}} a_{i_{2}} \cdots a_{i_{k}}}

It is thus sufficient to find a set of 2019 positive integers such that the geometric mean of every non-empty subset in an integer. Now, for an integer aa the number a2019!k=a2019!k\sqrt[k]{a^{2019!}}=a^{\frac{2019!}{k}} for all integers 1k20191 \leq k \leq 2019 so {12019!,22019!,,20192019!}\left\{1^{2019!}, 2^{2019!}, \ldots, 2019^{2019!}\right\} is a set such that the geometric mean of every non-empty subset is an integer.

b) Assume there exist such a set AA and let n,m,a1,a2,,am1n, m, a_{1}, a_{2}, \ldots, a_{m-1} be distinct elements in AA with n<mn<m. Then n+a1+a2++am1m\frac{n+a_{1}+a_{2}+\cdots+a_{m-1}}{m} and m+a1+a2++am1m\frac{m+a_{1}+a_{2}+\cdots+a_{m-1}}{m} are integers and also their difference

m+a1+a2++am1mn+a1+a2++am1m=mnm \frac{m+a_{1}+a_{2}+\cdots+a_{m-1}}{m}-\frac{n+a_{1}+a_{2}+\cdots+a_{m-1}}{m}=\frac{m-n}{m}

Therefore, we have nm\frac{n}{m} is an integer and since mm and nn are positive integers we have mnm \leq n which is a contradiction.

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.