I remember this problem from a movie.

“Twenty random cards are placed in a row, all face down. A move consists of turning a face down card, face up and turning over the card immediately to the right. Show that no matter what the choice of card to turn, this sequence of moves must terminate.”

Solution :

Consider each face down card as a 1 and each face up card as a 0. Initially, your sequence will be 11111111111111111111. Following the rule, each move will create a sequence whose binary value will be lower than the previous sequence. Eventually, all the cards will be facing up.

Let’s do a quick check in Python to verify this logic. 

import random
import matplotlib.pyplot as plt

Create a list of 20 1s.

L = [1]*20

L : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Copy this list so that the original list is undisturbed.

I = L[:]

I : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Let’s formulate the problem and check if it’s working.

for _ in range(10):
    
    idx = [i for i, x in enumerate(I) if x != 0]
    N = random.choice(idx)
    
    if N != 19:
        
        I[N], I[N+1] = 0, 1 - I[N+1]
        print(I)
        
    else:
        
        I[N] = 0
        print(I)

[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0]
[1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0]

Now this seems to work. Let’s run this till it terminates.

C = 0
S = [20]

while sum(I)!= 0:
    
    idx = [i for i, x in enumerate(I) if x != 0]
    N = random.choice(idx)
    
    if N != 19:
        
        C += 1
        I[N], I[N+1] = 0, 1 - I[N+1]
        S.append(sum(I))
    
    else:
        
        C += 1
        I[N] = 0
        S.append(sum(I))       
 
print(C)        
print(L)
print(I)

40
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Let’s plot the convergence.

plt.rcParams["figure.figsize"] = [16,9]
plt.grid()
plt.plot(S,'r^-')
plt.title('Convergence')
plt.xlabel('Moves')
plt.ylabel('Number of Face Down Cards')
plt.xlim(0, 60) 
plt.ylim(0, 20)
plt.show()

This took 40 moves. In the end, there are no face down cards.

When the same approach was repeated for 100 trials, on an average, it took 42 moves to converge.

– Pradeep