Digit-swapping game (own)
You and I are playing the following weird game: you start by swapping two random digits of the number 9876543210, then I swap two random digits of the new number, and we keep doing this alternatingly. Both of us are blindfolded so none of us knows what moves the other is playing. The first one to get 0123456789 wins. Can you ever win? When do I win?
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Digit-swapping game (own)
The problem seems interesting. But I need a clarification. I dont know what move you have played, doesn't it imply that I dont know what moves I played before? So, we forget all the moves and work only with the current state of the number.
Re: Digit-swapping game (own)
Err... I think you're right. But the problem is just asking if you can ever win, and to find the possible cases in which I win. Just assume that the moves are totally random and suppose that there is a referee who watches the game unless someone wins, who then stops the game and announces the winner.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Digit-swapping game (own)
I am still confused. Does RANDOM mean NO STRATEGY? I mean neither knows no winning strategy?
Re: Digit-swapping game (own)
I think no more explanation is needed, my first post explains everything you need to know. If that's not enough for you, the second post does the rest.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Digit-swapping game (own)
This can be generalized for all natural number $n$.
Let, for any permutation $(a_1,a_2,\cdots,a_n)$ of $(0,2,\cdots, n-1)$,
$f_n(a_1,a_2,\cdots,a_n) = \sum_{n > i \ge 0} {\left|\{\ j \ |\ j<i, a_j < a_i\ \}\right|}$
Then, it can be ( not so maybe ) easily verified that,
$f_n(\cdots,a_{i-1},a_i,a_{i+1},\cdots,a_{j-1},a_j,a_{j+1},\cdots) - f(\cdots,a_{j-1},a_j,a_{j+1},\cdots,a_{i-1},a_i,a_{i+1},\cdots) \equiv 1 \text{ mod } 2$
So, winning this game is only depends on whether $f(n-1,\cdots,0)=\frac{n(n-1)}{2}$ is odd or even
Let, for any permutation $(a_1,a_2,\cdots,a_n)$ of $(0,2,\cdots, n-1)$,
$f_n(a_1,a_2,\cdots,a_n) = \sum_{n > i \ge 0} {\left|\{\ j \ |\ j<i, a_j < a_i\ \}\right|}$
Then, it can be ( not so maybe ) easily verified that,
$f_n(\cdots,a_{i-1},a_i,a_{i+1},\cdots,a_{j-1},a_j,a_{j+1},\cdots) - f(\cdots,a_{j-1},a_j,a_{j+1},\cdots,a_{i-1},a_i,a_{i+1},\cdots) \equiv 1 \text{ mod } 2$
So, winning this game is only depends on whether $f(n-1,\cdots,0)=\frac{n(n-1)}{2}$ is odd or even
ধনঞ্জয় বিশ্বাস