Maths Olympiad Prep

Library / /314 of 397

Number theory Difficulty 6.7 National Olympiad Prove it Taiwan

Let nn be a positive integer, and let AA and BB be coprime positive integers such that
(n(n+1)2)!⋅∏k=1nk!(2k)!=BA. \left(\frac{n(n+1)}{2}\right)! \cdot \prod_{k=1}^{n} \frac{k!}{(2k)!} = \frac{B}{A}.
Prove that AA is a power of 22.

Solution

It suffices to prove that for all primes p≥3p \ge 3, we have
∑i=1∞([n(n+1)2pi]+∑k=1n([kpi]−[2kpi]))≥0 \sum_{i=1}^{\infty} \left( \left[ \frac{n(n+1)}{2p^i} \right] + \sum_{k=1}^{n} \left( \left[ \frac{k}{p^i} \right] - \left[ \frac{2k}{p^i} \right] \right) \right) \ge 0

Note that [2x]=[x]+[x+12][2x] = [x] + [x + \frac{1}{2}], so it suffices to prove for every positive integer ii that
[n(n+1)2P]≥∑k=1n[kP+12] \left[ \frac{n(n+1)}{2P} \right] \ge \sum_{k=1}^{n} \left[ \frac{k}{P} + \frac{1}{2} \right]

where P=piP = p^i is odd.

Case 1. n=Pa+b, 0≤b≤P−12n = Pa + b, \ 0 \le b \le \frac{P-1}{2},
R.H.S.=∑k=1n(kP+12)−P2⋅a−∑k=1b(kP+12)=n(n+1)2P+n2−Pa2−b(b+1)2P−b2=n(n+1)2P−b(b+1)2P \begin{aligned} \text{R.H.S.} &= \sum_{k=1}^{n} \left(\frac{k}{P} + \frac{1}{2}\right) - \frac{P}{2} \cdot a - \sum_{k=1}^{b} \left(\frac{k}{P} + \frac{1}{2}\right) \\ &= \frac{n(n+1)}{2P} + \frac{n}{2} - \frac{Pa}{2} - \frac{b(b+1)}{2P} - \frac{b}{2} \\ &= \frac{n(n+1)}{2P} - \frac{b(b+1)}{2P} \end{aligned}

Since n(n+1)2≡b(b+1)2(modP)\frac{n(n+1)}{2} \equiv \frac{b(b+1)}{2} \pmod{P}, we have
L.H.S.=[n(n+1)2P]≥n(n+1)2P−b(b+1)2P=R.H.S. \text{L.H.S.} = \left[ \frac{n(n+1)}{2P} \right] \ge \frac{n(n+1)}{2P} - \frac{b(b+1)}{2P} = \text{R.H.S.}

Case 2. n=Pa+P−12+b, 1≤b≤P−12n = Pa + \frac{P-1}{2} + b, \ 1 \le b \le \frac{P-1}{2},
R.H.S.=∑k=1n[P+2k2P]=∑k=1n(kP+12)−P2⋅a−∑k=1P−12(kP+12)−∑k=1b2k−12P=n(n+1)2P+n2−Pa2−12P⋅P−12⋅P+12−12⋅P−12−b22P=n(n+1)2P−(−b2+12P⋅P−12⋅P+12+b22P) \begin{align*} \text{R.H.S.} &= \sum_{k=1}^{n} \left[ \frac{P+2k}{2P} \right] \\ &= \sum_{k=1}^{n} \left( \frac{k}{P} + \frac{1}{2} \right) - \frac{P}{2} \cdot a - \sum_{k=1}^{\frac{P-1}{2}} \left( \frac{k}{P} + \frac{1}{2} \right) - \sum_{k=1}^{b} \frac{2k-1}{2P} \\ &= \frac{n(n+1)}{2P} + \frac{n}{2} - \frac{Pa}{2} - \frac{1}{2P} \cdot \frac{P-1}{2} \cdot \frac{P+1}{2} - \frac{1}{2} \cdot \frac{P-1}{2} - \frac{b^2}{2P} \\ &= \frac{n(n+1)}{2P} - \left( -\frac{b}{2} + \frac{1}{2P} \cdot \frac{P-1}{2} \cdot \frac{P+1}{2} + \frac{b^2}{2P} \right) \end{align*}

n(n+1)=(Pa+P−12+b)(Pa+P+12+b)=a2P2+aP⋅(P+2b)+(P−12+b)(P+12+b)=(a2+a)P2+2abP+P−12⋅P+12+Pb+b2≡P−12⋅P+12−Pb+b2(mod2P)≡(P−2b)2−14(mod2P) \begin{align*} n(n+1) &= \left(Pa + \frac{P-1}{2} + b\right)\left(Pa + \frac{P+1}{2} + b\right) \\ &= a^2 P^2 + aP \cdot (P + 2b) + \left(\frac{P-1}{2} + b\right)\left(\frac{P+1}{2} + b\right) \\ &= (a^2 + a)P^2 + 2abP + \frac{P-1}{2} \cdot \frac{P+1}{2} + Pb + b^2 \\ &\equiv \frac{P-1}{2} \cdot \frac{P+1}{2} - Pb + b^2 \pmod{2P} \\ &\equiv \frac{(P-2b)^2 - 1}{4} \pmod{2P} \end{align*}

L.H.S.=[n(n+1)2P]≥n(n+1)2P−12P((P−2b)2−14)=n(n+1)2P−(−b2+12P⋅P−12⋅P+12+b22P)=R.H.S., Q.E.D. \begin{align*} \text{L.H.S.} &= \left[ \frac{n(n+1)}{2P} \right] \ge \frac{n(n+1)}{2P} - \frac{1}{2P} \left( \frac{(P-2b)^2-1}{4} \right) \\ &= \frac{n(n+1)}{2P} - \left( -\frac{b}{2} + \frac{1}{2P} \cdot \frac{P-1}{2} \cdot \frac{P+1}{2} + \frac{b^2}{2P} \right) \\ &= \text{R.H.S.}, \text{ Q.E.D.} \end{align*}

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 translated into English from the original; metadata (topic, difficulty) added by this project.