Maths Olympiad Prep

Library / /379 of 860

Algebra Difficulty 5.1 AIME, harder Find the answer

Find the number of integers nn such that 1+100n101=99n100 1+\left\lfloor\frac{100 n}{101}\right\rfloor=\left\lceil\frac{99 n}{100}\right\rceil

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider f(n)=99n100100n101f(n)=\left\lceil\frac{99 n}{100}\right\rceil-\left\lfloor\frac{100 n}{101}\right\rfloor. Note that f(n+10100)=99n100+99101100n101+1002=f(n)+991011002=f(n)1f(n+10100)=\left\lceil\frac{99 n}{100}+99 \cdot 101\right\rceil-\left\lfloor\frac{100 n}{101}+100^{2}\right\rfloor=f(n)+99 \cdot 101-100^{2}=f(n)-1. Thus, for each residue class rr modulo 10100, there is exactly one value of nn for which f(n)=1f(n)=1 and nr(mod10100)n \equiv r(\bmod 10100). It follows immediately that the answer is 10100.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.