Maths Olympiad Prep

Library / /247 of 520

Number theory Difficulty 6.4 National olympiad Prove it

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

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 kp<2024kp < 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 - kp + 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

1. Let the numbers on the circle be a1,a2,,a2024a_1, a_2, \ldots, a_{2024}. Suppose bi!b_i! are a permutation of 1!,2!,,2024!1!, 2!, \ldots, 2024! for i=1,2,,2024i = 1, 2, \ldots, 2024. If this is possible, then ajaj+1=bj!a_j a_{j+1} = b_j! where a1=a2025a_1 = a_{2025}.

2. Consider the product of all the adjacent pairs:
b1!b2!b2024!=(a1a2)(a2a3)(a2023a2024)(a2024a1) b_1! b_2! \cdots b_{2024}! = (a_1 a_2) (a_2 a_3) \cdots (a_{2023} a_{2024}) (a_{2024} a_1)
This simplifies to:
(a1a2a3a2024)2 (a_1 a_2 a_3 \cdots a_{2024})^2
Let P=a1a2a2024P = a_1 a_2 \cdots a_{2024}. Then:
b1!b2!b2024!=P2 b_1! b_2! \cdots b_{2024}! = P^2

3. Let τ(n)\tau(n) be the total number of positive divisors of nn. We have:
τ(b1!b2!b2024!)=τ(P2) \tau(b_1! b_2! \cdots b_{2024}!) = \tau(P^2)
Since P2P^2 is a perfect square, τ(P2)\tau(P^2) is always odd.

4. Consider the prime number 661661. It divides:
b1!b2!b2024!=1!2!2024!=C b_1! b_2! \cdots b_{2024}! = 1! 2! \cdots 2024! = C
We need to find the exponent of 661661 in CC. Using Legendre's formula for the exponent of a prime pp in n!n!:
v661(C)=2024661+20246612+20246613+ v_{661}(C) = \left\lfloor \frac{2024}{661} \right\rfloor + \left\lfloor \frac{2024}{661^2} \right\rfloor + \left\lfloor \frac{2024}{661^3} \right\rfloor + \cdots
Calculating each term:
2024661=3,20246612=0(since 6612>2024) \left\lfloor \frac{2024}{661} \right\rfloor = 3, \quad \left\lfloor \frac{2024}{661^2} \right\rfloor = 0 \quad (\text{since } 661^2 > 2024)
Thus:
v661(C)=3 v_{661}(C) = 3

5. The number of divisors of CC is given by:
τ(C)=τ(1!2!2024!) \tau(C) = \tau(1! 2! \cdots 2024!)
Since v661(C)=3v_{661}(C) = 3, the factor 6613661^3 contributes 3+1=43+1 = 4 to τ(C)\tau(C). Therefore, τ(C)\tau(C) is even.

6. We have a contradiction because τ(C)\tau(C) must be even, but τ(P2)\tau(P^2) is odd. Therefore, Jane cannot accomplish her goal.

\blacksquare

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.