WEBVTT
Kind: captions
Language: en
00:00:13.670 --> 00:00:22.790
So, we are back and we are back with this
interesting puzzle, 15 puzzle and you know
00:00:22.790 --> 00:00:33.050
what we are supposed to do here? There are
15 small tildes and then there is empty space
00:00:33.050 --> 00:00:39.820
you can move your tildes in this case 3 or
7 to the empty space and like that empty space
00:00:39.820 --> 00:00:48.860
will be moving all across and eventually
you can shuffle reshuffle and bring it back
00:00:48.860 --> 00:00:57.220
to the same position so, 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15.
00:00:57.220 --> 00:01:02.500
So, what is the this is solved puzzle what
is unsolved puzzle for this? What is the scrambled
00:01:02.500 --> 00:01:12.270
1 some random sequence of some permutation
of numbers 1 to 15 and this place may be somewhere
00:01:12.270 --> 00:01:21.590
else; so, that is the thing.
Here is the question here is 1 configuration
00:01:21.590 --> 00:01:30.070
where you have all the numbers in order and
here you see these 2 have been swapped. Now
00:01:30.070 --> 00:01:37.189
the question is suppose this unjumpled versions
is given to you the scrambled version is given
00:01:37.189 --> 00:01:47.950
to you and then you are expected to make it
into the identity make it into the original
00:01:47.950 --> 00:01:57.009
position, can you do that as a question and
supposed to do it through when it moves you
00:01:57.009 --> 00:02:02.130
can just take the tiles out and later on
arrange it.
00:02:02.130 --> 00:02:09.200
So, to when it moves you are supposed to do
this. So, what do you see in this puzzle?
00:02:09.200 --> 00:02:28.760
You see of course, permutations and as you
recall we are talking of parity we are talking
00:02:28.760 --> 00:02:41.900
of invariant some quantity which is associated
to a configuration that remains unchanged
00:02:41.900 --> 00:02:50.849
as you go through valid moves as you play
the game as you go through this puzzle through
00:02:50.849 --> 00:02:55.850
valid moves second quantity which you associate
in certain abstract fashion is not going to
00:02:55.850 --> 00:02:59.220
change.
So, now there is a whole game whole game is
00:02:59.220 --> 00:03:07.250
about understanding what is the right kind
of invariant in the situation? So, answer
00:03:07.250 --> 00:03:15.900
to this is no, so in fact, that is what you
cannot reach from this configuration to this
00:03:15.900 --> 00:03:21.579
configuration of course, without breaking
the puzzle. So, you are not supposed to break
00:03:21.579 --> 00:03:30.390
it we are supposed to do only valid moves
and there was a research paper by these people
00:03:30.390 --> 00:03:35.670
Johnson and Story. So, what did Johnson and
Story do?
00:03:35.670 --> 00:03:43.930
They assigned an invariant to all possible
configurations some of them are possible configurations
00:03:43.930 --> 00:03:53.530
some of them are not. What you consider all
possible permutations in this. So, regard
00:03:53.530 --> 00:04:11.409
this North-East corner that is empty space
give us a notation phi. So, there are 16 symbols;
00:04:11.409 --> 00:04:20.870
1 to 15 and then empty set. So, these are
16 symbols where all this permutation is happening.
00:04:20.870 --> 00:04:35.410
And as you can see this particular configuration
the permutation is what? 3 phi 3 goes to phi
00:04:35.410 --> 00:04:42.320
phi goes to 3 and everything else is intact.
So, this is as you recall from the previous
00:04:42.320 --> 00:05:01.880
lectures this is transposition and its parity
or signature, signature of 3 phi is 1; signature
00:05:01.880 --> 00:05:11.560
of 3 phi 1 because there is only 1 is the
odd number 3, there is only 1 transposition
00:05:11.560 --> 00:05:14.950
which is used to express this particular permutation
ok.
00:05:14.950 --> 00:05:26.880
So, how do we assign the invariant in this
case? First you treat the solved puzzle as
00:05:26.880 --> 00:05:39.350
identity permutation and denote any valid
or invalid shuffled by x. So, this is x, this
00:05:39.350 --> 00:05:44.490
is x into x I am supposed to associate some
invariant.
00:05:44.490 --> 00:05:54.380
So, here is how I am doing it first parity
of the permutation x. So, this is as I said
00:05:54.380 --> 00:06:05.260
this is x and you as a parity of this transposition
1 plus taxicab distance, what is taxicab distance?
00:06:05.260 --> 00:06:25.720
Here is this North-East corner. So, here this
is just 1 step. Suppose every set were empty
00:06:25.720 --> 00:06:38.350
symbol were somewhere here then we just make
l shape. So, taxicab distance is some l shape
00:06:38.350 --> 00:06:47.440
thing, go from here to this. So, this is how
many steps; 1 step 2 step 3 step 4 steps right,
00:06:47.440 --> 00:06:52.270
but in this case for this particular x its
just 1 step.
00:06:52.270 --> 00:07:01.970
So, we do 1 class 1 and where do you do this
you do this? In the group z mod 2, so here
00:07:01.970 --> 00:07:10.590
you get 0. So, so to this particular configuration
the number that is going to be assigned or
00:07:10.590 --> 00:07:18.942
the element of the group z mod to z that is
going to be assigned is 0, the identity element.
00:07:18.942 --> 00:07:29.360
So, this is how you assigned to a given configuration
and element of z 2; this is the idea of those
00:07:29.360 --> 00:07:37.310
2 people Johnson and Story who published this
paper in American journal of mathematics 1879.
00:07:37.310 --> 00:07:47.340
That is a crucial observation that is a crucial
observation. So, when we play this game what
00:07:47.340 --> 00:07:56.190
is happening? Let us observe here and here;
here identity so, if you if you write f x
00:07:56.190 --> 00:08:04.020
for this particular x, how much is it? Identity
permutation whose signature or whose parity
00:08:04.020 --> 00:08:15.840
is 0 plus distance of phi from north east
corner which is 0. In the next step here for
00:08:15.840 --> 00:08:25.840
this particular x how much is parity how much
is the invariant it is 1 plus 1 which is
00:08:25.840 --> 00:08:37.710
again 0, this calculation is happening in
z mod 2 z mod 2 1 plus 1 equals 0.
00:08:37.710 --> 00:08:44.990
So, you can observe here. So, now let us take
one more situation. So, suppose 6 goes up
00:08:44.990 --> 00:09:08.480
that would be interesting 6 goes up. So, I
am just trying to so, since 6 goes up then
00:09:08.480 --> 00:09:16.750
you have 1 here 2 here 6 here 3 here empty
set here right, I am just swapping these 2
00:09:16.750 --> 00:09:35.310
in the next step and then 4 5 7 and then everything
else is intact 8 9 10 11 12 13 14 15. Suppose
00:09:35.310 --> 00:09:45.779
this is a configuration this is x then what
would f x be? So, to this x I am going to
00:09:45.779 --> 00:09:53.170
assign f x.
So, first of all we have to understand what
00:09:53.170 --> 00:10:03.120
permutation it is. So, in this permutation
1 2 4 5 8 9 10 11 12 13 14 15 all of them
00:10:03.120 --> 00:10:13.040
are intact. So, the only change that is happening
is here. So, let us write down the permutation.
00:10:13.040 --> 00:10:24.050
So, let us see. So, what is happening to phi,
phi goes to 6. What happens to 6? 6 goes to
00:10:24.050 --> 00:10:41.470
phi. So, over and that is on right, but here
are I have seen 3 and phi they have been exchanged.
00:10:41.470 --> 00:10:51.699
So, from the identity position first we did
the change of 3 and phi and then 6 and phi
00:10:51.699 --> 00:11:02.000
right. So, the signature of this, this
product of even number of permutations therefore,
00:11:02.000 --> 00:11:11.089
the signature will be 0. So, f x is 0 plus
the distance of empty set from the distance
00:11:11.089 --> 00:11:18.709
of empty symbol from northeast corner which
is 1 step and 2 step; 0 plus 2 and 0 plus
00:11:18.709 --> 00:11:24.560
2 is actually 0 mod 2 So, in z mod 2 this
is 0.
00:11:24.560 --> 00:11:32.100
So, f x is 0. So, f x is 0 here f x is 0 here
of x also 0 here. So, as you can easily observe
00:11:32.100 --> 00:11:43.670
as you play this game as you move according
to the valid moves the the quantity is 0 remains
00:11:43.670 --> 00:11:48.480
same; meaning if you assign the quantity in
this fashion which is parity of the permutation
00:11:48.480 --> 00:12:00.269
plus the distance of empty symbol from the
northeast corner that sum remains unchanged
00:12:00.269 --> 00:12:08.749
and one can actually conclude that if f x
is 1 then x is an invalid configuration. You
00:12:08.749 --> 00:12:16.180
cannot actually move from thus from the solved
puzzle to that particular configuration or
00:12:16.180 --> 00:12:22.089
from that particular configuration cannot
solve it in this fashion if f x is 1.
00:12:22.089 --> 00:12:28.019
Now, let us see what is there in this particular
situation. In this particular situation empty
00:12:28.019 --> 00:12:44.690
is here empty symbol is here and if I call
this configuration as x then what is f x,
00:12:44.690 --> 00:12:53.089
f x is the parity of this permutations. So,
here you would see from the origin the identity
00:12:53.089 --> 00:12:57.779
position there is a swapped; 14 and 15 have
been swapped. So, this is exactly 1. So, the
00:12:57.779 --> 00:13:07.790
15 and 14 they have been swapped.
So, the parity is 1, signature is 1 for the
00:13:07.790 --> 00:13:15.120
permutation and how much is the distance of
empty symbol from the northeast corner; it
00:13:15.120 --> 00:13:23.970
is 0. So, f x is 1 here and since f x is 1
this configuration is not possible. So, just
00:13:23.970 --> 00:13:31.589
with a very simple idea of parity and using
the group z mod 2 the group z 2 which has
00:13:31.589 --> 00:13:37.829
2 elements you could conclude quite easily
that this particular configuration is not
00:13:37.829 --> 00:13:43.459
possible; till that half the configurations
are possible half the configurations are not
00:13:43.459 --> 00:13:52.899
possible, that is why in another lecture as
mentioning about even permutations.
00:13:52.899 --> 00:14:04.600
And then we have this quite interesting
puzzle as I mentioned to you earlier Peg Solitaire.
00:14:04.600 --> 00:14:12.350
So, before I explain what it is let me
just play this puzzle ok we are going to play
00:14:12.350 --> 00:14:20.149
this and then I am going to come back to this.
So, this is Peg Solitaire and rules of the
00:14:20.149 --> 00:14:27.970
game as I was just mentioning during this
lecture. Here is empty space which is available
00:14:27.970 --> 00:14:36.800
I can pick say this 1 jump over this and knock
it out. Now there is some more space created
00:14:36.800 --> 00:14:43.689
I have option of doing something like this
and knock it out say something like this and
00:14:43.689 --> 00:14:49.019
knocking out.
So, here is the space I can do a knock out
00:14:49.019 --> 00:14:55.749
and eventually I am seeing what happens
in the end can I say as minimum as possible
00:14:55.749 --> 00:15:01.570
the number of marbles that are safe denied
they should be as less as possible. So, here
00:15:01.570 --> 00:15:23.579
I would request my TA Kanika to play this
game and show you if you can say won.
00:15:23.579 --> 00:16:39.610
Wow that is amazing ok great Kanika wonderful
great job. So, here you see the last one is
00:16:39.610 --> 00:16:54.269
here at the middle and just before that the
positions were like this and she jumped over
00:16:54.269 --> 00:16:58.649
this knocked it out and therefore, you have
last one here.
00:16:58.649 --> 00:18:16.551
Let me also try to play and see what happens
ok, Kanika you win. So, here you see the
00:18:16.551 --> 00:18:23.980
last 2 which have come they are at this position
the last ones which are saved are in these
00:18:23.980 --> 00:18:30.960
2 positions and the last single one was at
this position at the middle middle position.
00:18:30.960 --> 00:18:35.890
I can ask Kanika to do something difficult
thing which is I can challenge her if she
00:18:35.890 --> 00:18:43.330
can have last marble here single last marble,
but at this position and I am sure if he tries
00:18:43.330 --> 00:18:47.720
for couple of times she will declare that
its not possible.
00:18:47.720 --> 00:18:55.150
But how to logically arrive at that conclusion
we are going to learn through group theory
00:18:55.150 --> 00:19:00.630
and the group that we have already seen claims
for group the group of symmetries of rectangle
00:19:00.630 --> 00:19:06.620
very surprisingly that plays a role in the
rules of this game. So, I hope you enjoyed
00:19:06.620 --> 00:19:10.950
all that and now, lets come to the explanation
of it.
00:19:10.950 --> 00:19:17.870
So, this is our peg solitaire and as you have
seen what is one move? What constitutes one
00:19:17.870 --> 00:19:30.060
move here? So, there were 2 marbles I jumped
I from this marble to the empty space and
00:19:30.060 --> 00:19:36.650
in the process one marble was knocked out
right that is how we played all this and we
00:19:36.650 --> 00:19:47.460
just keep doing like this. Now my question
is in this game if you play like this? In
00:19:47.460 --> 00:19:55.330
the end we saw we could actually save one
marble and you remember what was the location
00:19:55.330 --> 00:20:06.150
of that marble, when as you could see its
possible to save one marble here.
00:20:06.150 --> 00:20:19.310
I change the question. I say ok, can you have
last one marble saved at this position or
00:20:19.310 --> 00:20:36.410
if I give you some configuration and ask you
that it is it possible to reach that configuration
00:20:36.410 --> 00:20:42.210
how will you answer that question? The answer
is quite surprising and shocking and in fact,
00:20:42.210 --> 00:20:48.460
the whole game has something to do with our
favourite group. We have seen this group couple
00:20:48.460 --> 00:20:59.290
of times Klein's 4 group, four element square
is 1, b square is 1, c square is also 1 into
00:20:59.290 --> 00:21:05.980
b c and so, on.
So, I hope you have understood the question,
00:21:05.980 --> 00:21:11.650
I just find some position I just some position
I just mark some position and they want last
00:21:11.650 --> 00:21:19.730
1 marble to be saved there at that position
and I hope you have also understood what the
00:21:19.730 --> 00:21:27.920
rules of the game are whenever you find empty
space you are allowed to jump like this and
00:21:27.920 --> 00:21:33.180
then knock out this marble, this marble goes
out this jumps and comes here and this is
00:21:33.180 --> 00:21:41.170
what you have.
So, that is a question the 1 marble is there
00:21:41.170 --> 00:21:49.990
what position is we will that have ok. So,
again here we are going to construct an invariant
00:21:49.990 --> 00:21:58.580
and interestingly this time the invariant
is going to take place in Klein's 4 group.
00:21:58.580 --> 00:22:09.430
So, to a given configuration to given arrangement
of marbles on the on the on on this game we
00:22:09.430 --> 00:22:16.710
are going to have we are going to associate
an element in the Klein's 4 group. How do
00:22:16.710 --> 00:22:24.570
we do that? It is quite smart quite interesting
and everything has to be realized here that
00:22:24.570 --> 00:22:44.930
somehow in this one move Klein's 4 group,
the Klein's 4 groups; group law is there ok.
00:22:44.930 --> 00:22:57.910
Let us do one very smart labeling. What
I do? I just start labeling these locations
00:22:57.910 --> 00:23:07.130
in cyclic fashion a b c and in b c a, then
a b c. So, that here also have a b c a b c
00:23:07.130 --> 00:23:22.460
a b c a then b c a b c a b c a b c a b c c
a b a b c. So, you read it like this or like
00:23:22.460 --> 00:23:31.090
this its quite cyclic ok.
So, if you pick 3 consecutive locations,
00:23:31.090 --> 00:23:40.340
one of them is a, one is b, one is c does
not matter I could have said b c a. So, a
00:23:40.340 --> 00:23:51.220
b c a b c this is there and then I am jumping
like this here and I am having this situation.
00:23:51.220 --> 00:24:05.690
Now what remains invariant here and that is
the main observation that is the main observation
00:24:05.690 --> 00:24:14.720
since I already mentioned Klein's 4 group
and those a b c; anyways of Klein's 4 group
00:24:14.720 --> 00:24:20.480
associated I am labeling using those a
3 labels.
00:24:20.480 --> 00:24:41.860
So, here if you observe we get the answer
of this namely the product of labels. So,
00:24:41.860 --> 00:25:02.490
product in Klein's 4 group where marble is
placed and this is what remains invariant
00:25:02.490 --> 00:25:11.140
is not it? You see marble is placed here and
here. So, b into c I have b into c which is
00:25:11.140 --> 00:25:16.910
a in a Klein's 4 group and here the marble
is placed only here, so product here is just
00:25:16.910 --> 00:25:25.140
a right and this is just one step. So, this
is a quantity which is being preserved here
00:25:25.140 --> 00:25:33.020
and other locations are anyway untouched in
one move and in one move this product is unchanged.
00:25:33.020 --> 00:25:41.410
So, that is easy how to decide how to associate,
how to assign an element in Klein's 4 group
00:25:41.410 --> 00:25:48.190
to a given configuration to a given distribution
of marbles on the board.
00:25:48.190 --> 00:25:58.310
So, as I said the key point treat as if a
b c are non trivial elements of Klein's 4
00:25:58.310 --> 00:26:06.120
group and the product of labels at occupied
positions those positions that marble is placed
00:26:06.120 --> 00:26:11.960
is not going to change throughout the game
that is crucial ok.
00:26:11.960 --> 00:26:16.680
So, the beginning the value of the initial
board if you call it or the invariant which
00:26:16.680 --> 00:26:24.120
is associated to the initial board is this,
except this location you have marble everywhere.
00:26:24.120 --> 00:26:33.990
So, I just take the product of all these things.
I am very fortunate here that Klein's 4 group
00:26:33.990 --> 00:26:42.840
is obedient. Therefore, I need not worry whether
it is a product a into b b into a the same
00:26:42.840 --> 00:26:47.340
thing.
So, I am just multiplying them. So, let me
00:26:47.340 --> 00:26:59.790
multiply them row by row. So, a into b
into c is e; e is identity, identity. So,
00:26:59.790 --> 00:27:09.530
a into b into c is e; this is also e and how
much is this, a into b into c is identity
00:27:09.530 --> 00:27:17.450
and a into b into c again identity and then
a. This is simply a, b into c into a I wont
00:27:17.450 --> 00:27:22.950
take this this is unoccupied position I am
considering only occupied position and now
00:27:22.950 --> 00:27:30.890
c into a into b which is e.
So, e is identity aims identity. I hope you
00:27:30.890 --> 00:27:36.770
are with me when I say a b c is identity.
How am I saying because a into b is c this
00:27:36.770 --> 00:27:46.170
c into c is actually e, c square is identity
right; that is what happens in Klein's 4 group
00:27:46.170 --> 00:27:53.570
and then c a b is identity c a b identity
c what remains is c and c a b is again identity,
00:27:53.570 --> 00:28:01.760
many a b c is again identity and then I take
the product of all these and what I have is
00:28:01.760 --> 00:28:11.450
a into c which is b right.
So, position of the initial the value of the
00:28:11.450 --> 00:28:21.120
initial board as per this assignment is b
and we known as we move along as per the valid
00:28:21.120 --> 00:28:28.230
moves this quantity is not going to change.
Whatever is the configuration what was the
00:28:28.230 --> 00:28:36.400
distribution of marbles over this board if
we assign to that the product of labels at
00:28:36.400 --> 00:28:44.840
occupied positions it is going to remain be
throughout and that is a key point.
00:28:44.840 --> 00:28:52.400
So, the value of product of label invariant
for the initial board is initial board it
00:28:52.400 --> 00:29:03.070
is b ok. That means what? That means, when
there is only 1 marble after playing this
00:29:03.070 --> 00:29:09.150
game. There only very few positions where
1 marble could be and that 1 marble could
00:29:09.150 --> 00:29:18.540
be at all these positions, wherever b is there
right. So, these are the only possibilities
00:29:18.540 --> 00:29:25.770
and does not mean that marble will be there
in the end, it is not there its not really
00:29:25.770 --> 00:29:34.320
required, but if at all 1 marble can be saved
then those positions could be some of these
00:29:34.320 --> 00:29:41.260
the other ones where a and c is there no no
single marble can can can be saved there
00:29:41.260 --> 00:29:47.840
in a.
And now, I make use of symmetry. I say that
00:29:47.840 --> 00:29:56.630
this is not a possibility and I mark it red.
How do I argue? I am arguing it because if
00:29:56.630 --> 00:30:03.020
this is the possibility then just imagine
as if you are playing in a mirror this would
00:30:03.020 --> 00:30:12.450
also be possibility right, but here I have
a, here the level is a and I know that I cannot
00:30:12.450 --> 00:30:19.220
have 1 marble here and therefore, just by
playing the game in the mirror we are forced
00:30:19.220 --> 00:30:27.250
to conclude that you cannot have marble here
in the end and then you are applied this argument
00:30:27.250 --> 00:30:32.120
and then you would conclude that all the b
is that I have marked with red they are actually
00:30:32.120 --> 00:30:35.520
not possible because if they are possible
if suppose this is possible again by playing
00:30:35.520 --> 00:30:40.710
in the mirror I should be able to save 1 marble
here.
00:30:40.710 --> 00:30:52.470
So, what are the uncrossed b's? Uncrossed
b's are these, only these and in the end when
00:30:52.470 --> 00:31:01.570
we saved 1 marble in the end and situation
was essentially like this. So, here you have
00:31:01.570 --> 00:31:09.360
2 options either take marble from here, put
it in the center knock out c or you take this
00:31:09.360 --> 00:31:15.920
marble from c to b knock out a and keep your
last marble here. So, these 2 are secondly
00:31:15.920 --> 00:31:21.620
positions and therefore, by symmetry all these
are actually possible positions where you
00:31:21.620 --> 00:31:28.280
can have marble 1 single marble in the end.
So, this very simple idea otherwise if we
00:31:28.280 --> 00:31:34.010
think it in some other fashion it could be
extremely complicated, but thanks to our observation
00:31:34.010 --> 00:31:43.510
what observation our observation that this
1 step is following the group law group law
00:31:43.510 --> 00:31:51.370
which is of Klein's 4 group that observation
we could stretch all across and we would
00:31:51.370 --> 00:31:59.440
conclude using the ideas of invariant that
the only possibility is there 1 marble could
00:31:59.440 --> 00:32:04.010
be same that these.
So, therefore, the last marble has to be there
00:32:04.010 --> 00:32:11.230
at a blue b there is no other position possible;
So, very simple ideas just very basic use
00:32:11.230 --> 00:32:19.610
of group theory, but when 1 of your connections.
You remember we started when we discussed
00:32:19.610 --> 00:32:25.630
Klein's 4 group, you started with the rectangle
and Klein's 4 group turned out to be symmetries
00:32:25.630 --> 00:32:31.290
of rectangle, but interestingly Klein's 4
group is also having beautiful applications
00:32:31.290 --> 00:32:42.010
in this in this puzzle.
So, I hope this was enjoyable for you and
00:32:42.010 --> 00:32:47.130
you would also devised some such games
you could change the rules of such games
00:32:47.130 --> 00:32:53.680
and try to discover if there is some other
group which is playing a role in that and
00:32:53.680 --> 00:32:59.400
you find such a thing please do write to us
and mean enjoy.
00:32:59.400 --> 00:33:00.370
Thank you.