# How to write a complete solution to this putnam problem (1985 , B3)?

$a_{ij}$ is a positive integer for $i,j=1,2,3,\ldots$, and for each positive integer we can find exactly eight $a_{ij}$ equal to it. Prove that $a_{ij}\gt ij$ for some $i,j$.

Proposed solution.

Solution. The idea is to show that for some $N$ there are more than $8N$ pairs $(i,j)$ with $ij\leq N$. For then, if we always had $a_{ij}\leq ij$ we would have $a_{ij}\leq N$ for more than $8N$ pairs, and some value in $\{1,2,\ldots,N\}$ would be shared by more than eight $a_{ij}$, contradicting the premise.

The number of of pairs $(i,j)$ with $ij\leq N$ is $$[N/1] + [N/2] + \cdots + [N/N] = N(1+ (1/2) + (1/3)+\cdots + (1/N)) -N,$$ but $\sum(1/n)$ diverges, so it is certainly greater than $9$ for sufficiently large $N$.

I don't understand this sloppy hint and I don't understand much in the problem. This was the problem I saved from another day. May someone help me and explain how that work? Thanks in advance.

-
Thank you, for making your question so self-contained. Please see this meta question. –  Arturo Magidin Oct 31 '11 at 2:58
It's not a hint, it's a solution; and I do not believe that it is in any way "sloppy". –  Arturo Magidin Oct 31 '11 at 3:06
@Arturo: I think replacing the greatest integer function $[\circ]$ with its argument $\circ$ and keeping the equality sign (instead of the $\ge$ sign, as it should be) is arguably "sloppy," but I think it's pretty trivial to "fix" it. –  anon Oct 31 '11 at 3:18
@anon: It's not merely being replaced with its argument (notice the $-N$ at the end); nonetheless, "the lady doth protest too much, methinks", especially given how sloppy the OP is in his own posts. Consider this, for example. –  Arturo Magidin Oct 31 '11 at 3:26
@Arturo: You're right, it's not just replaced with the argument, but the fact remains it's supposed to be an inequality rather than an equality. However you appear to also be right about the OP... –  anon Oct 31 '11 at 3:28

What is posted is not a "hint", it's a full solution. And there seems to be absolutely nothing "sloppy" about it.

Assume, in the interest of proving the statement by contrapositive, that the conclusion does not hold; that is, that for every pair $a_{i,j}$, we have $a_{i,j}\leq ij$. That means, for instance, that $a_{5,2}$ has to be a number in $\{1,2,\ldots,10\}$, because $a_{5,2}\leq 5\times 2 = 10$. We aim to show that there must be some positive integer $k$ for which there exist more than either pairs $(i,j)$ such that $a_{ij}=k$.

If $a_{ij}\leq ij$ for all $i$ and $j$, then that means that every $a_{ij}$ with $ij\leq N$ must be one of the numbers in $\{1,2,\ldots,N\}$. We know that each of these numbers corresponds to exactly eight $a_{ij}$. That means that there can be at most $8N$ pairs $(i,j)$ with $ij\leq N$; otherwise, the Pigeonhole Principle would tell you that there is at least one number in $\{1,2,\ldots,n\}$ that would correspond to more than $8$ pairs (because if you have only $8$ pairs per number, you would have at most $8N$ pairs, but you have strictly more than $8N$ pairs.

So the question now becomes: for a given $N$, how many pairs are there with $ij\leq N$?

Well, with $i=1$ you have $N$ pairs (namely, $(1,1)$, $(1,2)$, $(1,3),\ldots,(1,N)$).

For $i=2$, we have $\lfloor \frac{N}{2}\rfloor$ pairs, namely $(2,1)$, $(2,2)$, $(2,3),\ldots, (2,\lfloor \frac{N}{2}\rfloor)$.

For $i=3$, we have $\lfloor \frac{N}{3}\rfloor$ pairs.

And so on, until we get to $i=N$, when we have $1 = \lfloor \frac{N}{1}\rfloor$ pairs.

So the total number of pairs $(i,j)$ with $i$ and $j$ positive integers, and $ij\leq N$, is $$\left\lfloor \frac{N}{1}\right\rfloor + \left\lfloor \frac{N}{2}\right\rfloor + \cdots + \left\lfloor \frac{N}{N}\right\rfloor.$$

It is now straightforward, using the properties of the floor function, that you have: $$\left\lfloor \frac{N}{1}\right\rfloor + \left\lfloor \frac{N}{2}\right\rfloor + \cdots + \left\lfloor \frac{N}{N}\right\rfloor \geq N\left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{N}\right) - N.$$ Now, since $$\sum_{n=1}^{\infty}\frac{1}{n}$$ diverges, we can find an $N$ for which the sum $$\sum_{n=1}^N \frac{1}{n} = \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{N}$$ is greater than $9$. Then for that value of $N$, we have: $$N\left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{N}\right) - N \geq N(9) - N = 8N,$$ and that suffices, by the argument above, to show that there must be some number (specifically, an integer among $\{1,2,\ldots,N\}$ ) for which there are at least nine $a_{ij}$ that are equal to it. This proves the statement by contrapositive.

-

Here is a more explicit version of the solution:

There are 20410 pairs of positive integers $(i,j)$ with $ij \leq 2550$. However, there are only 2550 positive integers $k$ with $k \leq 2550$. Even allowing us to use each of these positive integers $k$ eight times only gives us 20400 possibilities. That leaves 10 pairs of positive integers $(i,j)$ with $ij \leq 2550$ that would then have to have $a_{ij} > 2550$ (by the Pigeonhole principle).

In particular, there is a list of 20410 pairs of $(i,j)$ that must contain at least 10 examples of the kind sought. The list looks a bit like:

$$\left\{ \begin{array}{rrrrr} (1,1), & (1,2), & (1,3), & \dots, & (1,2550), \\ (2,1), & (2,2), & (2,3), & \dots, & (2,1275), \\ (3,1), & (3,2), & (3,3), & \dots, & (3,850), \\ \dots \\ (50,1), & (50,2), & (50,3), & \dots, & (50,51), \\ (51,1), & (51,2), & (51,3), & \dots, & (51,50), \\ \dots \\ (2549,1) \\ (2550,1) \\ \end{array} \right\}$$

where the first row has 2550 entries, the second has 1275, the third has 850, the 50th has 51, the 51st has 50, and the last 1274 or so rows have 1 entry each.

Which particular entries in the list work depend on the exact nature of $a_{ij}$, we just know this list contains at least 10 examples.

-

All you have to do to make it rigorous is change the $=$ sign to a $>$ sign. What the solution might have gained by explaining is the following: $\alpha-[\alpha]<1$ for all $\alpha$ so we have $$[N/1]+[N/2]+\cdots+[N/N]>(N/1-1)+(N/2-1)+\cdots+(N/N-1)$$ $$=N(1+1/2+1/3+\cdots+1/N)-N=N\left(H_N-1\right).$$

-