-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathU1L6e.txt
130 lines (111 loc) · 4.04 KB
/
U1L6e.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#
# File: content-mit-8370x-subtitles/U1L6e.txt
#
# Captions for course module
#
# This file has 121 caption lines.
#
# Do not add or delete any lines. If there is text missing at the end, please add it to the last line.
#
#----------------------------------------
I'm going to call this the Mermin magic square game.
And before I'm going to do anything,
I'll give you a challenge.
Can you color the squares in a three by three grid
so every column has an odd number of red squares,
and every row has an even number of red squares?
Anybody, can you?
Well, let's try it.
So every column has to have an odd number of red,
green, green, green, red, green.
Now, every row has to have an even number,
so this had better be a red.
This had better be a red.
And this had better be a green.
But now, our last column doesn't work.
And in fact, if you think about this,
if every column has an odd number of red squares,
then there's a total odd number of red squares.
And if every row has an even number of red squares,
then there's an even number of red squares.
So you can't do it.
OK.
So now, I will give you our next game.
The referee sends one, two, three.
So he sends a number to Alice and another number to Bob.
And he chooses these numbers at random.
And they are between 1 and 3.
Alice give a coloring of the ith row of the grid.
So Alice might give if a equals 2, Alice might give,
and her row has to have an even number of red squares.
She might give green, red, red.
And Bob, let's call this the eighth row,
Bob gives the coloring of the bith row.
So b equals 1.
Bob might give red, green, green.
And they win.
Well, first they lose if either of them
doesn't have the right parity of a number of red squares
in his row or column.
And they also lose if the row and the column
don't agree in the square that they're match.
So they win if the row coloring and the column coloring
are legal.
And they agree in their overlap.
So do Alice and Bob have a deterministic strategy
that wins all the time?
Answer is no because if they did, you know,
if they had a determinacy strategy,
Alice would have her coloring of the square.
And she would just give the ith row to the referee
when she got i.
And Bob would have his coloring of the square.
And the two colorings of the square
would have to agree because any square might be in the overlap.
And the two colorings of the square
have to satisfy this that every column has
an odd number of red squares, and every row
has an even number of red squares.
So they can't win with probability 100.
So how often can Alice and Bob win?
Well, by the same--
Yeah?
Professor, can you do this again one more time.
OK.
So the referee gives a random column to Bob
and a random row to Alice.
Oh, you do it row and row, but it's column and row?
Yes.
Alice gets rows and Bob gets columns.
I'm sorry.
OK.
Yeah.
So Alice gets a row and Bob gets the column.
And they have to return a coloring.
And their two colorings have to agree where they overlap.
Well, we can assume that Alice and Bob each have
a deterministic strategy.
So suppose a deterministic strategy of Alice
had some row wrong.
Well, then she would lose the probability of 1/3
because whenever the referee asked her about that row,
she would return one with an odd number of red squares.
And the referee asked that row 1/3 of the time.
So to win with probability more than 2/3,
Alice must have a legal coloring of the rows.
And similarly, Bob must have a legally coloring
of the columns.
But Alice and Bob can't have a legal coloring
of both rows and columns because there is no such thing.
So what Alice and Bob have to do is
have two legal colorings that overlap
that agree as much as possible if they
want to win with the highest probability.
And that means they have to do something like green, red.
So these eight squares, Alice and Bob agree,
here, Alice will return a green, and Bob will return a red.
And this mean they lose with probability of 1/9
whenever this square is the one the referee chooses.
So whenever he gives a 3 to Bob and a 3 to Alice.
So the answer is 8/9.
But Alice and Bob can win with 100% probability