Morteza and Amir Reza play the following game. First each of them independently roll a dice $100$ times in a row to construct a $100$-digit number with digits $1,2,3,4,5,6$ then they simultaneously shout a number from $1$ to $100$ and write down the corresponding digit to the number other person shouted in their $100$ digit number. If both of the players write down $6$ they both win otherwise they both loose. Do they have a strategy with wining chance more than $\frac{1}{36}$? Proposed by Morteza Saghafian
Problem
Source: Iranian Combinatorics Olympiad 2020 P2
Tags: combinatorics, probability
ThE-dArK-lOrD
27.04.2020 21:19
Let $S$ be the set of all $100$-digit numbers whose digits are from $\{ 1,2,3,4,5,6\}$.
For each $x\in S$, let $x_{k}$ denote the $k$th digit of $x$, counting from left to right.
Let the two players shout the number $f(t)$ where $t$ is the $100$-digit number each of them get from their dice-rollings and $f$ is a function from $S$ to $\{ 1,2,\dotsc ,100\}$ defined by $$f(x)=\begin{cases}
\min \{ k\in \{ 1,2,\dotsc ,100\}\mid x_k=6\}, & \text{ if the set is not empty} \\
100, & \text{ otherwise}
\end{cases}$$for all $x\in S$.
To show that this strategy works, we need to show that
$$\sum_{a\in S}\sum_{b\in S} 1_{a_{f(b)}=6,b_{f(a)}=6} >\frac{6^{200}}{36}.$$This is true because
\begin{align*}
\sum_{a\in S}\sum_{b\in S} 1_{a_{f(b)}=6,b_{f(a)}=6} & \geqslant \sum_{a\in S}\sum_{b\in S}\sum_{k=1}^{99}{1_{f(a)=k,f(b)=k}}\\
& = \sum_{k=1}^{99}\left( 5^{k-1}\cdot 1 \cdot 6^{100-k}\right)^2 \\
& = \frac{6^{200}}{25} \sum_{k=1}^{99} \left( \frac{25}{36}\right)^k > \frac{6^{200}}{36}. \quad \blacksquare
\end{align*}
matinyousefi
27.04.2020 22:01
ThE-dArK-lOrD wrote:
Let $S$ be the set of all $100$-digit numbers whose digits are from $\{ 1,2,3,4,5,6\}$.
For each $x\in S$, let $x_{k}$ denote the $k$th digit of $x$, counting from left to right.
Let the two players shout the number $f(t)$ where $t$ is the $100$-digit number each of them get from their dice-rollings and $f$ is a function from $S$ to $\{ 1,2,\dotsc ,100\}$ defined by $$f(x)=\begin{cases}
\min \{ k\in \{ 1,2,\dotsc ,100\}\mid x_k=6\}, & \text{ if the set is not empty} \\
100, & \text{ otherwise}
\end{cases}$$for all $x\in S$.
To show that this strategy works, we need to show that
$$\sum_{a\in S}\sum_{b\in S} 1_{a_{f(b)}=6,b_{f(a)}=6} >\frac{6^{200}}{36}.$$This is true because
\begin{align*}
\sum_{a\in S}\sum_{b\in S} 1_{a_{f(b)}=6,b_{f(a)}=6} & \geqslant \sum_{a\in S}\sum_{b\in S}\sum_{k=1}^{99}{1_{f(a)=k,f(b)=k}}\\
& = \sum_{k=1}^{99}\left( 5^{k-1}\cdot 1 \cdot 6^{100-k}\right)^2 \\
& = \frac{6^{200}}{25} \sum_{k=1}^{99} \left( \frac{25}{36}\right)^k > \frac{6^{200}}{36}. \quad \blacksquare
\end{align*}
To prove that the strategy works we can see that the chance of $f(x)=1$ for both strings is $\frac{1}{36}$ and the chance of $f(x)=2$ for both strings is non-zero hence the conclusion.
AwesomeYRY
26.07.2021 22:43
This is quite cool.
Each player's strategy is as follows. If their first number is a 6, they shout 1, and if their first number isn't a 6, they shout 2. This wins if either both start with 6, or with both start with $x6$ with $x\neq 6$, so we can guarantee a winning probability of at least
\[\left(\frac16\right)^2 + \left(\frac56 \cdot \frac16 \right)^2 > \frac{1}{36} \]and so we are done. $\blacksquare$
Remark: I have no idea what the upper bound is, I feel like you extend this quite a bit.
JustKeepRunning
28.07.2021 21:26
Darn this problem has a pretty cool idea behind it. Although the answer to this problem was yes, suppose the answer had actually been no? How could you possibly prove that the answer is no to a question like this?