How many times must we roll a single die in order to get the same score n times for $n\ge 4$?
I thought the answer was $6n + 1$ but the answer is $6 (n-1)+1$ and I don't really get why is that.
My professor's reasoning is this but I'm not fully understanding the $(n – 1)$ part.
"First we will construct a lower bound. If we have $6 (nā1)$ objects then we can have $n – 1$ occurrences of each outcome. To construct the upper bound, we can use generalized pigeon principle on $ 6(n ā 1) + 1$ objects. As there are 6 boxes (die outcomes), we obtain:
$\left\lceil\frac{(6 (n ā 1) + 1)} 6\right\rceil = (n – 1) + 1 = n$
So some outcome will be rolled n times for $6 (n ā 1) + 1$ die rolls."
I think it has to do with my understanding of lower bound and upper bound. Anyone care to break it down a little bit more for me?
Best Answer
I'm gonna explain it in my own style.
The answer is $6(n-1)+1$.
Why?
Clearly if we roll $6(n-1)+1$ times, at least one of the six possible outcomes appears $n$ times or more. Otherwise each outcome appears at most $n-1$ times. So in total there would be at most $6(n-1)$rolls, a contradiction, since we rolled $6(n-1)+1$ times.
What do we conclude? If we roll $6(n-1)+1$ times at least one outcome appears $n$ times or more.
Can we roll less times and still be sure at least one outcome appears $n$ times or more? No we cannot, suppose we roll $6(n-1)$ times.
It is possible that each appears $n-1$ times.
So the minimum number of times we must roll a single die in order to be certain we get at least one score $n$ times or more is $6(n-1)+1$