1

Having trouble understanding a solution to a textbook problem.

A computer randomly prints three-digit codes, with no repeated digits in any code. What is the minimum number of codes that must be printed in order to guarantee that at least six of the codes are identical?

I have the solution,

$^{10} P_{3} = (10)(9)(8) = 720$ distinct values
The minimum number of codes is $5\times ^{10} P_{3} + 1 = 3601$

I don't understand why $n$ is being multiplied by $5$ and added with $1$. To my understanding, having $726$ codes would ensure that $6$ of them are repeated. So why does the value need to be multiplied and added to?

MyNameIs
  • 17
  • The question asks for at least six of the codes are identical. $123$, e.g. is a code that is allowed to occur upto $5$ times. Same for every other possible code. Thus $5\cdot 720 +1$ – true blue anil Dec 06 '16 at 10:39

2 Answers2

1

The idea is that you want to guarantee to have one code printed six times.

So, for example, with $3600$ print outs you could potentially have every code printed exactly five times. This is why you need to have at least $3601$ to guarantee one code being printed six times.

hexomino
  • 1,571
0

Let the number of codes printed randomly by the computer denote by $N$ (objects). By the rule of product there are $10\times 9\times 8 = 720$ different three-digit codes (boxes). By the generalized pigeonhole principle we need to find the smallest

$$N \in \mathbb Z^{+} : \lceil \frac{N}{720} \rceil \geq 6$$

Hence, we have,

$ \min$ {$ N | \lceil \frac{N}{720} \rceil \geq 6$} = $\min$ {$ N| \frac{N}{720} +1 > 6$} = $\min$ { $N | \frac{N}{720} > 6−1$} = $\min$ {$ N | N \geq 5\times 720+1 $} $= 3601$. Hope it helps.