10
$\begingroup$

8 standard six-sided dice with faces numbered 1, 2, 3, 4, 5, 6 each are thrown at the same time and the product of the dice is written down on a paper. This process is repeated until you are able to select two numbers on the paper, whose product is a square number.

In the worst case, how many repetitions are required to achieve this?

$\endgroup$
19
$\begingroup$

The only prime factors of the numbers 1 through 6 are 2, 3, and 5. Therefore the factorization of the numbers on the paper will only consist of these primes, i.e. they will be of the form:

$$ 2^a 3^b 5^c $$

for nonnegative integers $a$, $b$, and $c$ (the exponents).

A number is square if and only if its exponents are all even. Consider one of the exponents, say $a$. If we multiply a number with exponent $a_1$ with a number with exponent $a_2$, the resulting exponent is $a_1+a_2$. This is even only if both $a_i$ are even or both $a_i$ are odd. Therefore if we split the numbers into two groups based on the parity of $a$, we can only pick two whose product is a square if they belong to the same group.

Now since we have three prime factors, there are 8 different groups with the $2^3$ different combinations of even and odd for each exponent. Therefore we might be able to pick 8 numbers, one from each group, such that none of the pairwise products are square, but if we pick 9, then by the pigeonhole principle we are guaranteed to pick two in the same group and we will be able to make a square.

In fact we can pick 8 numbers such that there is no square product, e.g. 1, 2, 3, 5, 6, 10, 15, and 30; therefore the worst-case number of times we need to roll the dice is 9.

$\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.