Olympiad Maths Prep

Library / /11 of 16

Number theory Difficulty 6.3 National olympiad Prove it Czech Republic

123n1 \cdot 2 \cdot 3 \cdot \dots \cdot n
*is written on a blackboard. For which positive integers* n2n \ge 2 *can we append the exclamation mark to some factors and change it to factorials in such a way that the final product will be a square?*

Solution

Let us denote vp(n)v_p(n) the highest power of a prime pp which divides positive integer nn. This function has obviously the following properties:
- For all primes pp and positive integers nn is vp(n)v_p(n) non-negative integer.
- For all positive integers m,nm, n and all primes pp is vp(mn)=vp(m)+vp(n)v_p(mn) = v_p(m) + v_p(n).
- For all primes pp is vp(p!)=vp(p)=1v_p(p!) = v_p(p) = 1.
- For all primes pp is vp((p+1)!)=1v_p((p+1)!) = 1, vp(p+1)=0v_p(p+1) = 0.
- For all primes pp and all positive integers n<pn < p is vp(n!)=vp(n)=0v_p(n!) = v_p(n) = 0.
- Positive integer nn is a square if and only if vp(n)v_p(n) is even (including zero) for all primes pp.

Let us denote S=n!S = n! the initial value of the product on the table and SS' its final value after adding factorials. We can easy to see from the properties of vpv_p that for nn is equal to any prime pp we obtain vp(S)=vp(p!)=1v_p(S) = v_p(p!) = 1 and vp(S)=1v_p(S') = 1, because adding factorials does not change the amount of the prime pp (= nn) in the final product on the blackboard. The number vp(S)v_p(S') is then odd and therefore SS' is not a square.

Let us assume that nn is a composite number (so n4n \ge 4) in whole of the following part. We will show that we can add factorials in such a way that the final product
S=f1f2f3fn, S' = f_1 \cdot f_2 \cdot f_3 \cdots f_n,
will be a square, where fkf_k is either kk or k!k! for all kk. It is equivalent to vp(S)v_p(S') is even for all primes pp. Since nn is not a prime, only primes less than nn occur in the product SS'. As every such primes pp are not in factors f1,f2,,fp1f_1, f_2, \dots, f_{p-1} and the prime pp occurs in fpf_p only once, the final power vp(S)v_p(S') is the same as in a “reduced” product
pfp+1fp+2fn.(1) p \cdot f_{p+1} \cdot f_{p+2} \cdots f_n. \qquad (1)
How can we provide that every prime p<np < n will occur in the corresponding product (1) with even power? Since in the second factor fp+1f_{p+1} from (1) occurs the prime pp either once (in the case fp+1=(p+1)!f_{p+1} = (p+1)!) or the prime pp does not occure (if fp+1=p+1f_{p+1} = p+1), we can provide “good” occurrence of pp by choice of fp+1f_{p+1} independently on succeeding values fp+2,,fnf_{p+2}, \dots, f_n.

Foregoing analysis gives us construction of the required choice of factorials. Initially we choose fk{k,k!}f_k \in \{k, k!\} arbitrarily for all knk \le n such that k1k-1 is not a prime. The other fkf_k, it is fp+1f_{p+1}, where pp is arbitrary prime less than nn, will be chosen “backwards”, from the biggest such prime pp to the smallest prime p=2p = 2. For the biggest unchosen fp+1f_{p+1} we find parity of vp(fp+2fn)v_p(f_{p+2} \dots f_n), in odd case we choose fp+1=p+1f_{p+1} = p+1, in even case we choose fp+1=(p+1)!f_{p+1} = (p+1)! and so on.

This finishes the construction of SS' and solution of the problem too.

Conclusion. Desired n2n \ge 2 are all composite numbers.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.