Let $ n$ be a given positive integer. Find the smallest positive integer $ u_n$ such that for any positive integer $ d$, in any $ u_n$ consecutive odd positive integers, the number of them that can be divided by $ d$ is not smaller than the number of odd integers among $ 1, 3, 5, \ldots, 2n - 1$ that can be divided by $ d$.
Problem
Source: CWMO 2003, Problem 3
Tags: modular arithmetic, pigeonhole principle, number theory unsolved, number theory
28.09.2011 00:45
I think the wording of the problem is quite confusing.. not unclear, just confusing. I'd reword it: Let $n$ be a positive integer. Define the set $N_{m,k}$, where $m$ is an odd positive integer, to be the set of the $k$ smallest odd integers that are at least $m$. For an arbitrary positive integer $d$, denote by $N_{m,k}(d)$ the number of integers in the set $N_{m,k}$ that are divisible by $d$. Find the smallest $u_n\in\mathbb{N}$ (in terms of $n$) such that $N_{m,u_n}(d)\ge N_{1,n}(d)$ for every positive integer $d$ and odd positive integer $m$. Perhaps this is an even more confusing way of putting it! Feel free to choose the version with the better exposition. Anyway, the first few values for $u_n$ are $1,3,5,7,9$ so we conjecture $u_n=2n-1$. Clearly $N_{1,n}(2n-1)=1$ because of the presence of $2n-1$ in the set $N_{1,n}$. As the next odd multiple is $3(2n-1)=2(3n-1)-1$, this means that $N_{2n+1,2n-2}(2n-1)=0$. So $u_n\ge 2n-1$. We now need to show $u_n=2n-1$ works. Note that $N_{1,n}(d)=0$ for $d\not\in\{1,3,5,\ldots ,2n-1\}$ so we only need to worry about $d$ in this set. Now let $m$ be an arbitrary odd positive integer. Then the set $N_{m,2n-1}$ consists of the integers $m,m+2,m+4,\ldots ,m+2(2n-1)-2$. One of the first $d$ of these integers is divisible by $d$. Suppose on the other hand none of the first $d$ integers are multiples of $d$. Then none are equal to $0\pmod{d}$ and so by pigeonhole there are two equal $\pmod{d}$, say $m+a$ and $m+b$ where $0\le a<b\le 2d-2$. This means $d|b-a$. Of course, $2d-2\ge b-a>0$ and so the only multiple of $d$ that $b-a$ can possibly be is $d$ itself (the case $d=1$ can be discarded). Now $a$ and $b$ are both even, so $b-a$ is even, meaning $d$ is even, contradiction, as we assumed $d\in\{1,3,5,\ldots ,2n-1\}$. And so the assertion that one of the first $d$ of these integers is divisible by $d$ is correct. So let $m+a$ be the smallest integer in the set $N_{m,2n-1}$ such that $d|m+a$. We have just proven $a\le 2d-2$. Let $h$ be the largest integer such that $m+a+2hd\le m+4n-4$. Then the integers in $N_{m,2n-1}$ which are divisible by $d$ are $m+a,m+a+2d,m+a+4d,\ldots ,m+a+2hd$. It follows that $N_{m,2n-1}(d)=h+1$. Now let $b$ be the largest odd integer such that $bd\le 2n-1$, and if $b=2c-1$ then it follows that $N_{1,n}(d)=c\ge 1$. Now $(2c-1)d\le 2n-1$ so $2(2c-1)d\le 4n-2$. Now since $h$ is the largest integer such that $m+a+2hd\le m+4n-4$, we have $a+2(h+1)d\ge 4n-4$. Now $2d-2\ge a$ meaning $2d-2+2(h+1)d\ge a+2(h+1)d\ge 4n-4\ge 2(2c-1)d-2$. Then it follows that $h+1\ge 2c-2\ge c$ for $c>1$. When $c=1$, we have $d=2n-1$ in which case $h=0$ so $h+1=1\ge 1=c$. So $h+1\ge c$. So $N_{m,2n-1}(d)\ge N_{1,n}(d)$ , proving that $u_n=2n-1$.