Let $n$ be a positive integer. There is an infinite number of cards, each one of them having a non-negative integer written on it, such that for each integer $l \geq 0$, there are exactly $n$ cards that have the number $l$ written on them. A move consists of picking $100$ cards from the infinite set of cards and discarding them. Find the least possible value of $n$ for which there is an infinitely long series of moves such that for each positive integer $k$, the sum of the numbers written on the $100$ chosen cards during the $k$-th move is equal to $k$.
Problem
Source:
Tags: combinatorics
28.10.2015 02:05
Pretty nice. The minimum is $10000$. Generalize slightly; pick $j$ cards at each step rather than $100$. We want to find the minimum $n$ in terms of $j$. For each $k$, the first $kj$ cards we pick have sum $1+2+\cdots+k=\frac{k(k+1)}{2}$. That means that there have to be $kj$ available cards with that sum. The $dn$ cards with the smallest numbers on them have sum $(n\cdot 0+n\cdot 1+\cdots+n\cdot d)=n\frac{d(d-1)}{2}$. So, is the smallest possible sum of cards less than or equal to the sum of the cards we need? To avoid dealing with remainders, we specialize a bit and choose $k$ divisible by $n$; say, $k=an$, with $a$ an integer. Then the sum of the first $anj$ cards chosen is $\frac{an(an+1)}{2}$, and the smallest possible sum of $anj$ cards is $n\frac{aj(aj-1)}{2}$. For this to be possible, we must have \begin{align*}n\frac{aj(aj+1)}{2} &\le \frac{an(an+1)}{2}\\ n(a^2j^2+aj)&\le a^2n^2+an\\ (j^2n-n^2)a^2+(jn-n)a&\le 0\end{align*}Choose $a$ large. If the coefficient of $a^2$ were positive, the inequality would fail, so we must have $j^2n-n^2\le 0$. This gives $n\ge j^2$. Now that we know we can't do it with $n$ less than $j^2$, we need something in the other direction. Can we construct a choice of cards that works when $n=j^2$? Yes. Specifically, if $k$ divided by $j$ gives a quotient of $q$ and a remainder of $r$, we take $j-r$ copies of $q$ and $r$ copies of $q+1$ at step $k$. Over the entire process, we take $j-1+(j-2)+\cdots+2+1=\frac{j(j-1)}{2}$ copies of zero and $1+2+\cdots+(j-1)+j+(j-1)+\cdots+2+1=j^2$ copies of each other number. The construction works, and we're done.