Maths Olympiad Prep

Library / /871 of 1394

, 2019

Number theory Difficulty 5.4 AIME, harder Prove it United States

Problem:

Call a positive integer nn weird if nn does not divide (n2)!(n-2)!. Determine the number of weird numbers between 2 and 100 inclusive.

Solution

Solution:

We claim that all the weird numbers are all the prime numbers and 44.

Since no numbers between 11 and p2p-2 divide prime pp, (p2)!(p-2)! will not be divisible by pp. We also have 2!=22! = 2 not being a multiple of 44.

Now we show that all other numbers are not weird. If n=pqn = pq where pqp \neq q and p,q2p, q \geq 2, then since pp and qq both appear in 1,2,,n21, 2, \ldots, n-2 and are distinct, we have pq(n2)!pq \mid (n-2)!. This leaves the only case of n=p2n = p^2 for prime p3p \geq 3. In this case, we can note that pp and 2p2p are both less than p22p^2 - 2, so 2p2(n2)!2p^2 \mid (n-2)! and we are similarly done.

Since there are 2525 prime numbers not exceeding 100100, there are 25+1=2625 + 1 = 26 weird numbers.

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.