Maths Olympiad Prep

Library / /4 of 24

Number theory Difficulty 5.6 AIME, harder Prove it Canada

Problem:

Jane writes down 2024 natural numbers around the perimeter of a circle. She wants the 2024 products of adjacent pairs of numbers to be exactly the set {1!,2!,,2024!}\{1!, 2!, \ldots, 2024!\}. Can she accomplish this?

Solutions — 2

Solution 1

Solution:

Given any prime pp and positive integer xx, let vp(x)v_{p}(x) denote the highest power of pp dividing xx. We claim that Jane cannot write 2024 such numbers as that would imply that 1!2!2024!1! \cdot 2! \cdots 2024! is the square of the product of the 2024 numbers. Let pp be a prime and kk be a natural number such that k<pk < p, kp2024k p \leq 2024, and (k+1)p>2024(k+1) p > 2024. Then note that
vp(1!2!2024!)=(2024p+1)+(20242p+1)++(2024kp+1) v_{p}(1! \cdot 2! \cdots 2024!) = (2024 - p + 1) + (2024 - 2p + 1) + \ldots + (2024 - k p + 1)
In particular, let pp be in (20244,20242)\left(\frac{2024}{4}, \frac{2024}{2}\right). By Bertrand's Postulate, such a prime pp exists (and pp must also be odd). Further, the corresponding kk is either 2 or 3. Either way, vp(1!2!2024!)v_{p}(1! \cdot 2! \cdots 2024!) is odd from the above formula, and so 1!2!2024!1! \cdot 2! \cdots 2024! cannot be a perfect square.

Solution 2

Solution:

As in the first solution, we prove 1!2!2024!1! \cdot 2! \cdots 2024! is not a perfect square. To do this, note that we can rewrite the product as (1!)22(3!)24(2023!)22024(1!)^{2} \cdot 2 \cdot (3!)^{2} \cdot 4 \cdots (2023!)^{2} \cdot 2024 which is
242024(1!3!2023!)2=1012!(210121!3!2023!)2 2 \cdot 4 \cdots 2024 \cdot (1! \cdot 3! \cdots 2023!)^{2} = 1012! \cdot \left(2^{1012} \cdot 1! \cdot 3! \cdots 2023!\right)^{2}
so it is sufficient to verify 1012!1012! is not a perfect square. This can be verified by either noticing the prime 10091009 only appears as a factor of 1012!1012! once, or by evaluating v2(1012!)=1005v_{2}(1012!) = 1005.

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.