#ThisWeeksFiddler, 20260918

Skriv en kommentar

This week the #puzzle is: Can You Swap the Cups? #average #ExpectedValue #montecarlo #coding

My friend has three cups, labeled “A,” “B,” and “C” in a row. She randomly picks two different cups and swaps their positions. Then she does this again and again, picking a random pair each time, until all three cups are back in their original order. For example, here is one such sequence of swaps:
– A, B, C (original)
– C, B, A (first and third were swapped)
– B, C, A (first and second were swapped)
– B, A, C (second and third were swapped)
– A, B, C (first and second were swapped)
In this example, the cups returned to their original order after four swaps.
On average, how many swaps would you expect until the cups return to their original order?

And for extra credit:

In total, there are six possible orders of the cups. Without any swaps, one of those orders (A, B, C) has already been achieved.
On average, how many swaps would you expect until the remaining five orders (and thus, all six) are also achieved?

Can You Swap the Cups?

Intermission

So, last week was not good.

  • I didn’t read the instructions correctly. I thought the 1st quiz had 4 questions, not 3.
  • I did notice other answers using strategies involving “if the 1st correct answer was A, there’s a slightly better chance the 3rd answer is A”, but I didn’t understand why this could be until the official answer was out.

Solution, possibly incorrect:

Program

Method 1: Ye olde monte carlo. This time I play around with variance and deviation calculations, so that the program will keep going, until I get the number of decimals, I want.

======================================
Number of loops.... 3 * :    102970102
Target deviation........:    0.0010000
Deviations so far, res 1:    0.0003204
======================================
Final result 1..........:    5.9999515 +/-  0.0003204

Result: 6.00. Maybe simply 6?

Method 2: Look closely at what’s going on. This is a diagram of all states and all changes between states.

And that’s a little… Wait, that can actually be shown in a better way.

“abc” is the beginning state. Each line represents 1 swap. How many steps does it take to get from a state back to the beginning state?

sabc=0s_{abc}=0

If we’re already in the beginning state, 0 steps.

scba=13⋅(1+sabc)+23⋅(1+sleft)s_{cba}=\frac{1}{3}\cdot(1+s_{abc})+\frac{2}{3}\cdot (1+s_{left})

Here I’ve called “a state on the left that isn’t the beginning state” “left”. 1/3 of the time, take 1 step and get back to the beginning state. 2/3 of the time, take 1 step and reach a left state. And actually, let’s call all the states on the right “right”.

sright=13⋅(1+sabc)+23⋅(1+sleft)s_{right}=\frac{1}{3}\cdot(1+s_{abc})+\frac{2}{3}\cdot (1+s_{left})

sleft=1+srights_{left}=1+s_{right}

In a left state, I have to take 1 step to get to a right state. Let’s solve this.

sabc=0,sright=13⋅(1+sabc)+23⋅(1+sleft),sleft=1+srights_{abc}=0,s_{right}=\frac{1}{3}\cdot(1+s_{abc})+\frac{2}{3}\cdot (1+s_{left}),s_{left}=1+s_{right}

sright=13⋅(1+0)+23⋅(1+1+sright)s_{right}=\frac{1}{3}\cdot(1+0)+\frac{2}{3}\cdot (1+1+s_{right})

sright=13+43+23⋅srights_{right}=\frac{1}{3}+\frac{4}{3}+\frac{2}{3}\cdot s_{right}

13⋅sright=53\frac{1}{3}\cdot s_{right}=\frac{5}{3}

sright=5s_{right}=5

There’s always a 1st step, away from the beginning state. And then it will take 5 further steps/swaps to get back. That’s 6. Result confirmed.

And for extra credit:

Same program, I just use the data slightly differently.

======================================
Number of loops.........:    102970102
Target deviation........:    0.0010000
Deviations so far, res 2:    0.0005949
======================================
Final result 2..........:   12.2144230 +/-  0.0005949

Result: 12.21 – 12.22.

Method 2. Let me see. First some new notation.

sxys_{xy}

How many steps left on average, when there’s x already visited states on “my” side (WLOG the left side) of the diagram and y on the other?

s33=0s_{33}=0

If both sides are already full, there are 0 steps left.

s23=6s_{23}=6

This is the same situation as the fiddler. Being in one of the lower states on the left side and aiming for (WLOG) the top state of the left.

s32=5s_{32}=5

This was the intermediate situation above, taking 1 step away from the coveted state.

Let’s just summarize.

sx3s_{x3}sx2s_{x2}sx1s_{x1}sx0s_{x0}
s3ys_{3y}05n/a
s2ys_{2y}6n/a
s1ys_{1y}
s0ys_{0y}n/an/an/an/a

Some of these situations are impossible. Typically, I can’t have visited 2-3 states on one side of the diagram and 0 on the other. Also, x can’t be 0, because I am in a state, that is therefore visited.

Right!

s31=13⋅(1+s13)+23⋅(1+s23)s_{31}=\frac{1}{3}\cdot (1+s_{13})+\frac{2}{3}\cdot (1+s_{23})

s22=13⋅(1+s32)+23⋅(1+s22)s_{22}=\frac{1}{3}\cdot(1+s_{32})+\frac{2}{3}\cdot(1+s_{22})

s13=1+s31s_{13}=1+s_{31}

Let’s solve this.

s23=6,s31=13⋅(1+s13)+23⋅(1+s23),s13=1+s31s_{23}=6,s_{31}=\frac{1}{3}\cdot (1+s_{13})+\frac{2}{3}\cdot (1+s_{23}),s_{13}=1+s_{31}

s31=13⋅(1+1+s31)+23⋅(1+6)s_{31}=\frac{1}{3}\cdot (1+1+s_{31})+\frac{2}{3}\cdot (1+6)

s31=23+13⋅s31+143s_{31}=\frac{2}{3}+\frac{1}{3}\cdot s_{31}+\frac{14}{3}

23⋅s31=163\frac{2}{3}\cdot s_{31}=\frac{16}{3}

s31=8s_{31}=8

And:

s31=8,s13=1+s31s_{31}=8,s_{13}=1+s_{31}

s13=1+8s_{13}=1+8

s13=9s_{13}=9

And:

s22=13⋅(1+s32)+23⋅(1+s22),s32=5s_{22}=\frac{1}{3}\cdot(1+s_{32})+\frac{2}{3}\cdot(1+s_{22}),s_{32}=5

s22=13⋅(1+5)+23⋅(1+s22)s_{22}=\frac{1}{3}\cdot(1+5)+\frac{2}{3}\cdot(1+s_{22})

s22=2+23+23⋅s22s_{22}=2+\frac{2}{3}+\frac{2}{3}\cdot s_{22}

13⋅s22=83\frac{1}{3}\cdot s_{22}=\frac{8}{3}

s22=8s_{22}=8

Let’s summarize again.

sx3s_{x3}sx2s_{x2}sx1s_{x1}sx0s_{x0}
s3ys_{3y}058n/a
s2ys_{2y}68n/a
s1ys_{1y}9
s0ys_{0y}n/an/an/an/a

s21=13⋅(1+s12)+23⋅(1+s22)s_{21}=\frac{1}{3}\cdot (1+s_{12})+\frac{2}{3}\cdot(1+s_{22})

s12=13⋅(1+s31)+23⋅(1+s21)s_{12}=\frac{1}{3}\cdot (1+s_{31})+\frac{2}{3}\cdot(1+s_{21})

Solving.

s21=13⋅(1+s12)+23⋅(1+s22),s12=13⋅(1+s31)+23⋅(1+s21),s22=8,s31=8s_{21}=\frac{1}{3}\cdot (1+s_{12})+\frac{2}{3}\cdot(1+s_{22}),s_{12}=\frac{1}{3}\cdot (1+s_{31})+\frac{2}{3}\cdot(1+s_{21}),s_{22}=8,s_{31}=8

s21=13⋅(1+s12)+23⋅(1+8),s12=13⋅(1+8)+23⋅(1+s21)s_{21}=\frac{1}{3}\cdot (1+s_{12})+\frac{2}{3}\cdot(1+8),s_{12}=\frac{1}{3}\cdot (1+8)+\frac{2}{3}\cdot(1+s_{21})

s21=13+13⋅s12+6,s12=3+23+23⋅s21s_{21}=\frac{1}{3} + \frac{1}{3}\cdot s_{12} +6,s_{12}=3+\frac{2}{3}+\frac{2}{3}\cdot s_{21}

s21=613+13⋅s12,s12=113+23⋅s21s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot s_{12} ,s_{12}=\frac{11}{3}+\frac{2}{3}\cdot s_{21}

s21=613+13⋅s12,s12−113=23⋅s21s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot s_{12} ,s_{12}-\frac{11}{3}=\frac{2}{3}\cdot s_{21}

s21=613+13⋅s12,32(s12−113)=s21s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot s_{12} ,\frac{3}{2}(s_{12}-\frac{11}{3})=s_{21}

s21=613+13⋅s12,32⋅s12−32⋅113=s21s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot s_{12} ,\frac{3}{2}\cdot s_{12}-\frac{3}{2}\cdot\frac{11}{3}=s_{21}

s21=613+13⋅s12,32⋅s12−112=s21s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot s_{12} ,\frac{3}{2}\cdot s_{12}-\frac{11}{2}=s_{21}

613+13⋅s12=32⋅s12−1126\frac{1}{3} + \frac{1}{3}\cdot s_{12} =\frac{3}{2}\cdot s_{12}-\frac{11}{2}

19+s12=92⋅s12−33219 + s_{12} =\frac{9}{2}\cdot s_{12}-\frac{33}{2}

19+332=72⋅s1219 + \frac{33}{2}=\frac{7}{2}\cdot s_{12}

712=72⋅s12\frac{71}{2}=\frac{7}{2}\cdot s_{12}

71=7⋅s1271=7\cdot s_{12}

717=s12\frac{71}{7}=s_{12}

And:

717=s12,s21=613+13⋅s12\frac{71}{7}=s_{12}, s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot s_{12}

s21=613+13⋅717s_{21}=6\frac{1}{3} + \frac{1}{3}\cdot \frac{71}{7}

s21=957s_{21}=9\frac{5}{7}

And summarizing:

sx3s_{x3}sx2s_{x2}sx1s_{x1}sx0s_{x0}
s3ys_{3y}058n/a
s2ys_{2y}689579\frac{5}{7}n/a
s1ys_{1y}9101710\frac{1}{7}
s0ys_{0y}n/an/an/an/a

Almost there!

s11=13⋅(1+s11)+23⋅(1+s21)s_{11}=\frac{1}{3}\cdot (1+s_{11})+\frac{2}{3}\cdot(1+s_{21})

Solving:

s11=13⋅(1+s11)+23⋅(1+s21),s21=957s_{11}=\frac{1}{3}\cdot (1+s_{11})+\frac{2}{3}\cdot(1+s_{21}),s_{21}=9\frac{5}{7}

s11=13⋅(1+s11)+23⋅(1+687)s_{11}=\frac{1}{3}\cdot (1+s_{11})+\frac{2}{3}\cdot(1+\frac{68}{7})

s11=13+13⋅s11+23⋅757s_{11}=\frac{1}{3} + \frac{1}{3} \cdot s_{11}+\frac{2}{3}\cdot\frac{75}{7}

3⋅s11=1+s11+2⋅7573 \cdot s_{11}=1 + s_{11}+2\cdot\frac{75}{7}

2⋅s11=15772 \cdot s_{11}=\frac{157}{7}

s11=15714s_{11}=\frac{157}{14}

sx3s_{x3}sx2s_{x2}sx1s_{x1}sx0s_{x0}
s3ys_{3y}058n/a
s2ys_{2y}689579\frac{5}{7}n/a
s1ys_{1y}9101710\frac{1}{7}1131411\frac{3}{14}
s0ys_{0y}n/an/an/an/a

Whew! Only one more.

s10=1+s11s_{10}=1+s_{11}

Solving:

s10=1+s11,s11=11314s_{10}=1+s_{11},s_{11}=11\frac{3}{14}

s10=12314≈12.2143s_{10}=12\frac{3}{14} \approx 12.2143

This was the number, we were looking for. And it confirms the previous result.

Just to finish the table:

sx3s_{x3}sx2s_{x2}sx1s_{x1}sx0s_{x0}
s3ys_{3y}058n/a
s2ys_{2y}689579\frac{5}{7}n/a
s1ys_{1y}9101710\frac{1}{7}1131411\frac{3}{14}1231412\frac{3}{14}
s0ys_{0y}n/an/an/an/a

Skriv en kommentar