2001 APMO Problems/Problem 2

Problem

Find the largest positive integer $N$ so that the number of integers in the set $\{1,2,\dots,N\}$ which are divisible by 3 is equal to the number of integers which are divisible by 5 or 7 (or both).

Solution

The equation $\left\lfloor\frac{N}{3}\right\rfloor=\left\lfloor\frac{N}{5}\right\rfloor+ \left\lfloor\frac{N}{7}\right\rfloor-\left\lfloor\frac{N}{35}\right\rfloor$ is equivalent to the problem statement. The period (of remainders of $N$ ) is the least common multiple of all denominators, which is $105$ . We perform casework on an easier bound, namely $35$ . Listing all lesser multiples of $3,5,7$ : $3,5,6,7,9,10,12,14,15,18,20,21,24,25,27,28,30,33,35$ Next, we number each of these values with a positive integer that describes by how much the left-hand side of the above equation is greater than the right-hand side: $1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0$ Notice that $35$ counts only once (since it is one number), but $15,21,$ and $30$ all count twice (since they are on different sides of the equation, they cancel out).

Next, we list out until $70$ : $36,39,40,42,45,48,49,50,51,54,55,56,57,60,63,65,66,69,70$ and we number the values again (initially $0$ , since that is what we ended with): $1,2,1,1,1,2,1,0,1,2,1,0,1,1,1,0,1,2,1$ Finally, we list out until $105$ : $72,75,77,78,80,81,84,85,87,90,91,93,95,96,98,99,100,102,105$ and we number the values: $2,2,1,2,1,2,2,1,2,2,1,2,1,2,1,2,1,2,2$ (All of the above really make sense if you manipulate the equation such that it is equal to zero and set it to $y$ in a Desmos graph.)

The difference should then repeat from $n=1$ but will start instead at $2$ . Thus, it will never equate again (since the difference in the first cycle is never negative). As a result, the largest $N$ such that the two sides are equal is $\boxed{65}$ from our data above.

~ eevee9406

Page

Toolbox

Search

2001 APMO Problems/Problem 2

Problem

Solution