2
$\begingroup$

Each of the six faces of a die is marked with an integer, not necessarily positive. The die is rolled $1000$ times. Show that there is a time interval such that the product of all rolls in this interval is a cube of an integer. (For example, it could happen that the product of all outcomes between 5th and 20th throws is a cube; obviously, the interval has to include at least one throw!)

I looked at abcdef as a possible product , somehow $1000$ of these 'terms' no matter how we shuffle them , a product like ababab or adadad or acdacdacd will be in the string but i cant prove how :(

$\endgroup$
10
$\begingroup$

We can show something stronger; there exists an interval of rolls where each side has appeared a number of times which is a multiple of $3$.

For each $i=1,2,\dots,1000$, let $a_i$ be number of times that the first face has appeared in rolls numbered $1,2,\dots,i$. Same for $b_i,c_i,d_i,e_i,f_i$. Consider the $1000$ ordered six-tuples of values $T_i:=(a_i,b_i,\dots,f_i)$, where each coordinate is only recorded modulo $3$. There are $3^6=729$ possible six-tuples, and there are $1000$ rolls, so by the pigeonhole principle, there are two indices $i<j$ for which $T_i=T_j$. This implies that among rolls numbered $i+1,i+2,\dots,j$, each face appears a number of times which is a multiple of three.

$\endgroup$
  • $\begingroup$ i dont get it, how again can u use pigeonhole? and how does this work for cubes not 3k $\endgroup$ – Randin D Apr 25 at 4:32
  • $\begingroup$ (a) There are $1000$ numbers $i\in\{1,2,\dots,1000\}$, and $729$ possible tuples. $1000$ pigeons in $729$ holes. (b) If each face appears a multiple of three times, and the numbers of the faces are $x,y,z,w,s,t$, then the product of the numbers in that interval $[i+1,j]$ is $x^{3i}y^{3j}\cdots t^{3k}$, which is the cube of $x^iy^j\cdots t^k$. $\endgroup$ – Mike Earnest Apr 25 at 4:36
  • $\begingroup$ i get pigeonhole ..1000 into 729 means 3 will be in one pigeonhole right? and thats the cube? $\endgroup$ – Randin D Apr 25 at 4:39
  • $\begingroup$ how do u get the 729 again? $\endgroup$ – Randin D Apr 25 at 4:41
  • $\begingroup$ Do you understand my sentence that starts with “Consider...”? We keep track of the remainder of the number of times each face appears in the first $i$ rolls modulo 3. There are three possible remainders, and six faces, so $3^6$. The reason this is helpful is because if the number of times the $a$ face appears in the first $i$ rolls is $3m+r$, and in the first $j$ rolls is $3n+r$, then subtracting, the number of times $a$ appears after $i$ and up to $j$ is $3(n-m)$, which is a multiple of $3$. $\endgroup$ – Mike Earnest Apr 25 at 16:02
1
$\begingroup$

Strengthening the result another way:

For each $i=1,\dots,1000$ let $2^{a_i}\cdot 3^{b_i}\cdot 5^{c_i}$ be the product of the first $i$ rolls. Then there are only $3^3=27$ possible values for the 3-tuple $(a_i\bmod 3, b_i\bmod 3, c_i\bmod 3)$, so, by a pigeonhole principle argument similar to Mike Earnest's in his answer, a cube must appear if there are more than 27 rolls.

$\endgroup$
  • $\begingroup$ The question specifies that the sides of the die might be numbered with any integers, not necessarily just 1, 2, 3, 4, 5 and 6. I believe the worst case would be one where each side is numbered with a distinct prime. $\endgroup$ – Ilmari Karonen Apr 25 at 9:04
  • $\begingroup$ @IlmariKaronen OK, good point, now that I see that in the OP. $\endgroup$ – Rosie F Apr 25 at 9:05

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.