11
$\begingroup$

The famulus of a mathematical meta magician puts infinitely many cards into a top hat.
Each of these cards carries a non-negative integer. The top hat contains

  • exactly $n$ cards showing the integer $0$,
  • exactly $n$ cards showing the integer $1$,
  • exactly $n$ cards showing the integer $2$,
  • exactly $n$ cards showing the integer $3$,
  • exactly $n$ cards showing the integer $4$,
  • and so on.

Then the mathematical meta magician starts removing cards from the top hat.

  • In the $1$st step, the magician takes ten cards with total value $1$.
  • in the $2$nd step, the magician takes ten cards with total value $2$,
  • in the $3$rd step, the magician takes ten cards with total value $3$,
  • in the $4$th step, the magician takes ten cards with total value $4$,
  • in the $5$th step, the magician takes ten cards with total value $5$,
  • and so on,
  • in the $k$th step, the magician takes ten cards with total value $k$,
  • and so on.

Question: What is the smallest possible integer $n$, for which the mathematical meta magician can make an infinite number of such steps (without ever getting stuck)?

$\endgroup$
14
$\begingroup$

The following shows the optimal way to pull numbers out the hat, showing every $1$ that is used. Below, $n$ is $100$. This can obviously be continued forever.

0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1 2 2 2
1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 2 2 2 2 2
1 1 1 1 2 2 2 2 2 2
1 1 1 2 2 2 2 2 2 2
1 1 2 2 2 2 2 2 2 2
1 2 2 2 2 2 2 2 2 2

All that remains to be shown is that there is no way to do this with only $99$ copies of each card. Notice that on the $k^{th}$ day, the magician has drawn $10k$ cards with average value $\frac{k+1}{20}$. However, we can also bound the average of the first $10k$ cards, and if this is greater than $\frac{k+1}{20}$, the magician can't do their trick. In particular consider the $cn^{th}$ step. The lowest $10cn$ cards will be numbered from $0$ to $10c-1$, each having a set of $n$ cards. Thus, they average to $\frac{10c}2=5c$. This yields that we must have $$\frac{cn+1}{20}\geq 5c$$ $$cn+1 \geq 100 c$$ meaning $n\geq 100$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.