Difference between revisions of "2001 APMO Problems/Problem 2"

(Problem)
 
(solution)
 
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 
Find the largest positive integer <math>N</math> so that the number of integers in the set <math>\{1,2,\dots,N\}</math> which are divisible by 3 is equal to the number of integers which are divisible by 5 or 7 (or both).
 
Find the largest positive integer <math>N</math> so that the number of integers in the set <math>\{1,2,\dots,N\}</math> which are divisible by 3 is equal to the number of integers which are divisible by 5 or 7 (or both).
 +
 +
==Solution==
 +
The equation
 +
<cmath>\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</cmath>
 +
is equivalent to the problem statement. The period (of remainders of <math>N</math>) is the least common multiple of all denominators, which is <math>105</math>. We perform casework on an easier bound, namely <math>35</math>. Listing all lesser multiples of <math>3,5,7</math>:
 +
<cmath>3,5,6,7,9,10,12,14,15,18,20,21,24,25,27,28,30,33,35</cmath>
 +
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:
 +
<cmath>1,0,1,0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,0</cmath>
 +
Notice that <math>35</math> counts only once (since it is one number), but <math>15,21,</math> and <math>30</math> all count twice (since they are on different sides of the equation, they cancel out).
 +
 +
Next, we list out until <math>70</math>:
 +
<cmath>36,39,40,42,45,48,49,50,51,54,55,56,57,60,63,65,66,69,70</cmath>
 +
and we number the values again (initially <math>0</math>, since that is what we ended with):
 +
<cmath>1,2,1,1,1,2,1,0,1,2,1,0,1,1,1,0,1,2,1</cmath>
 +
Finally, we list out until <math>105</math>:
 +
<cmath>72,75,77,78,80,81,84,85,87,90,91,93,95,96,98,99,100,102,105</cmath>
 +
and we number the values:
 +
<cmath>2,2,1,2,1,2,2,1,2,2,1,2,1,2,1,2,1,2,2</cmath>
 +
(All of the above really make sense if you manipulate the equation such that it is equal to zero and set it to <math>y</math> in a Desmos graph.)
 +
 +
The difference should then repeat from <math>n=1</math> but will start instead at <math>2</math>. Thus, it will never equate again (since the difference in the first cycle is never negative). As a result, the largest <math>N</math> such that the two sides are equal is <math>\boxed{65}</math> from our data above.
 +
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]

Latest revision as of 23:10, 20 March 2025

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