Maths Olympiad Prep

Library / CMO /4 of 22

CMO

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, kp≤2024k p \leq 2024, and (k+1)p>2024(k+1) p > 2024. Then note that
vp(1!⋅2!⋯2024!)=(2024−p+1)+(2024−2p+1)+…+(2024−kp+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!)2⋅2⋅(3!)2⋅4⋯(2023!)2⋅2024(1!)^{2} \cdot 2 \cdot (3!)^{2} \cdot 4 \cdots (2023!)^{2} \cdot 2024 which is
2⋅4⋯2024⋅(1!⋅3!⋯2023!)2=1012!⋅(21012⋅1!⋅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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.