Let n be a given positive integer. Find the smallest positive integer un such that for any positive integer d, in any un 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,…,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 Nm,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 Nm,k(d) the number of integers in the set Nm,k that are divisible by d. Find the smallest un∈N (in terms of n) such that Nm,un(d)≥N1,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 un are 1,3,5,7,9 so we conjecture un=2n−1. Clearly N1,n(2n−1)=1 because of the presence of 2n−1 in the set N1,n. As the next odd multiple is 3(2n−1)=2(3n−1)−1, this means that N2n+1,2n−2(2n−1)=0. So un≥2n−1. We now need to show un=2n−1 works. Note that N1,n(d)=0 for d∉{1,3,5,…,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 Nm,2n−1 consists of the integers m,m+2,m+4,…,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.