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).
Problem
Source: APMO 2001
Tags: number theory, counting, floor function
19.03.2006 10:28
we want $[\frac{N}{3}] = [\frac{N}{5}]+[\frac{N}{7}]-[\frac{N}{35}]$. let $N = 105k+r$, where $0\leq r < 105$. then our relation becomes $35k+[\frac{r}{3}] = 21k+15k-3k+[\frac{r}{5}]+[\frac{r}{7}]-[\frac{r}{35}]$; or $2k = [\frac{r}{5}]+[\frac{r}{7}]-[\frac{r}{35}]-[\frac{r}{3}]$. now, the RHS is $< 2+104(\frac15+\frac17-\frac{1}{35}-\frac{1}{3})=2-104\cdot\frac{2}{105} = \frac{2}{105}$. so $k=0$ and $N = r < 105$ and the remaining details are too boring to fill in
19.03.2006 10:49
It is equavalent to $[\frac N3 ]+[\frac{N}{35}]=[\frac N5]+[\frac N7].$ Let $a=N(mod 3),b=N(mod35),c=b(mod 5),d=b(mod 7)$. We have $\frac{2N}{105}=\frac a3 +\frac{b}{35} -\frac c5 -\frac d7$. Maximum expression $\frac{b}{35}-\frac c5 -\frac d7$ is $\frac{14}{35}$ (b=21). Maximum $\frac a3=\frac 23$. Therefore $N=105(2/3+14/35)/2=56$.
22.06.2007 05:58
Hey Rust, I think you are wrong because $[\frac{65}{3}] =[\frac{65}{5}]+[\frac{65}{7}]-[\frac{65}{35}]$
18.08.2011 08:45
03.12.2016 23:28
We can set really bad bounds on the right hand side and left hand side of $[\frac{N}{3}] = [\frac{N}{5}]+[\frac{N}{7}]-[\frac{N}{35}]$ and find the largest value from there. We have that $[\frac{N}{3}] \geq \frac{N}{3} - \frac{2}{3}$ and $[\frac{N}{5}]+[\frac{N}{7}]-[\frac{N}{35}] < \frac{N}{5}+\frac{N}{7}-\frac{N}{35}+1 $. From this, we get that the equality is broken for all N that satisfy $\frac{N}{3} - \frac{2}{3} > \frac{N}{5}+\frac{N}{7}-\frac{N}{35}+1$ which is equivalent to $n>67.5$ From here, it is easy to see that 65 is the largest number that works and is our answer.
04.12.2016 00:39
Let f(n) = [n/3] - [n/5] - [n/7] + [n/35]. We are looking for the largest n with f(n) = 0. Now [n/5] + [n/7} <= [n/5 + n/7] = [12n/35] = [n/3 + n/105]. So for [n/5] + [n/7] to exceed [n/3] we certainly require n/105 ≥ 1/3 or n ≥ 35. Hence f(n) ≥ 0 for n ≤ 35. But f(n+35) = [n/3 + 11 + 2/3] - [n/5 + 7] - [n/7 + 5] + [n/35 + 1] = [n/3 + 2/3] - [n/5] - [n/7] + [n/35] ≥ f(n) (*). Hence f(n) ≥ 0 for all n. But f(n+105) = [n/3 + 35] - [n/5 + 21] - [n/7 + 15] + [n/35 + 3] = f(n) + 2. Hence f(n) ≥ 2 for all n ≥ 105. Referring back to (*) we see that f(n+35) > f(n), and hence f(n+35) > 0, unless n is a multiple of 3. But if n is a multiple of 3, then n + 35 is not and hence f(n+70) > f(n+35) > 0. So f(n) > 0 for all n ≥ 70. f(70) = 1. So f(69) = 2 (we have lost 70, a multiple of 7). So f(68) = f(67) = f(66) = 1 (we have lost 69, a multiple of 3). Hence f(65) = 0 (we have lost 66, a multiple of 3). Answer: 65.
01.09.2023 21:49
This issue is equivalent floor(N/3)=floor(N/5)+floor(N/7)-floor(N/35) * N/3-2/3<=floor(N/3)<=N/5+N/7-N/35+34/35 so N<=86 we can note N=35 work so N=35+k where 0<=k<=51 now Equation * equivalent floor((k+2)/3)=floor(k/5)+floor(k/7)- floor(k/35) From this we can see that floor(k/35)<=k/105<1 so k=<34 and floor((k+2)/3)=floor(k/5)+floor(k/7) And it's easy to check that k=30 is the biggest solution and N=65 is the solution