WEBVTT
Kind: captions
Language: en
00:00:14.530 --> 00:00:17.300
.
So we are back and as I promised, we are going
00:00:17.300 --> 00:00:23.300
to have some fun with these 3 glasses and
I am going to use group action to solve one
00:00:23.300 --> 00:00:32.591
problem. First, let me ask you the problem
we have 3 inverted cups and at one time I
00:00:32.591 --> 00:00:40.820
can pick 2 of them and change their orientations.
So, if they are inverted, I can make them
00:00:40.820 --> 00:00:53.089
upright and then keep doing like that I take
any any of them maybe this I am back .
00:00:53.089 --> 00:01:02.809
So, my purpose is to make all all 3 of them
upright by doings, and I am just trying it
00:01:02.809 --> 00:01:12.100
and I am trying hard it is not happening I
cannot do that. I have tried to be couple
00:01:12.100 --> 00:01:16.420
of times 10 times something, but even if you
tried thousand times it is not going to happen.
00:01:16.420 --> 00:01:25.219
And why does it? Why is it the case? Why I
cannot make all all 3 of them up right? So,
00:01:25.219 --> 00:01:32.350
it is a question for that let me first convince
you that there is some group action which
00:01:32.350 --> 00:01:36.520
is going on here.
So, whenever there is group action there is
00:01:36.520 --> 00:01:43.979
a group and then there is a set . So, this
is one configuration how many such configurations
00:01:43.979 --> 00:01:53.039
are possible ? These are 3 and there are 2
positions for each of these glasses 2 to
00:01:53.039 --> 00:01:59.609
the power 3 8 configurations are possible
and as I had indicated. In the last lecture
00:01:59.609 --> 00:02:09.950
, look at it this sequence of 0's and 1's
there is some similarity right. So, we can
00:02:09.950 --> 00:02:25.730
say 0 is the inverted position
and say 1 is the upright position. So this
00:02:25.730 --> 00:02:36.000
set which we constructed as a group , let
us take it as a set. This is set of all configurations
00:02:36.000 --> 00:02:46.620
which are possible for these 3 classes.
So, this is set of all configurations all
00:02:46.620 --> 00:02:55.930
possible configurations and on the set of
configurations. What is acting right? I am
00:02:55.930 --> 00:03:01.629
acting right it is a group there is a group
which is acting which is changing these
00:03:01.629 --> 00:03:09.299
configurations. So, here is an interesting
idea you can see they are the same, you remember
00:03:09.299 --> 00:03:18.530
clients 4 group as I have been mentioning
and this time we denote it by 1, a, b, c there
00:03:18.530 --> 00:03:26.340
are 4 elements in these group, as you recall
a square is identity b square is identity
00:03:26.340 --> 00:03:42.510
c square is identity and then abc ac is b
and b c is a
00:03:42.510 --> 00:03:51.579
it is Abelian group so, abc is same as b a
similarly this is same as ca and same as cb
00:03:51.579 --> 00:04:03.189
of course, a square, b square, c square is
I think. So, what I am saying is that this
00:04:03.189 --> 00:04:13.849
group has something to do with this problem.
So, I define the group action exactly in the
00:04:13.849 --> 00:04:23.550
same way as I am playing this game V4 is acting
on X. What is x axis? All possible configurations
00:04:23.550 --> 00:04:34.470
and then there should be an action. So, let
us pick an element from V4 well if there element
00:04:34.470 --> 00:04:45.920
is identity then whatever I pick from X, I
pick something like say 101 or then it is
00:04:45.920 --> 00:04:53.680
simply 101 nothing is happening interesting
thing is for example, when I pick a from V4
00:04:53.680 --> 00:05:02.120
and then what is it is effect on say 1 0 0
that is what I am going to explain.
00:05:02.120 --> 00:05:09.509
So, effect of a on 1 0 0 is that, this position.
So, let us call it position a, position b,
00:05:09.509 --> 00:05:18.319
position c. So, position a is unchanged while
2 other positions are swapped. So, 0 becomes
00:05:18.319 --> 00:05:28.970
1, 1 becomes 0. So,1 0 0 becomes 1 1 1. So,
if I have this to be 1, 1 is upright position
00:05:28.970 --> 00:05:43.639
0 is inverted position. So, if a is 1and b
is 0 and c is 1 .
00:05:43.639 --> 00:05:56.470
So, if I have this, then identity is not doing
anything to it yeah and here say 1 0 0. So,
00:05:56.470 --> 00:06:06.949
it is 1 a 0 and c 0. So, when I apply on this
configuration the element a from the client's
00:06:06.949 --> 00:06:16.900
4 group what happens? All 3 become upright
. So, I take I do not touch a, I touch only
00:06:16.900 --> 00:06:24.960
other 2 and I just change their position.
So, all 3 become upright if I take something
00:06:24.960 --> 00:06:35.729
else say, I take say b and consider how b
is going to act with say 110 .
00:06:35.729 --> 00:06:47.360
So, I am not supposed to touch sorry so I
am not supposed to touch b. So, this one will
00:06:47.360 --> 00:06:56.169
remain intact while the 2 other will be swept
so 1 becomes 0 and this 0 becomes 1. So, it
00:06:56.169 --> 00:07:06.830
becomes 011 so let us see so the 110 meaning
a is upright, b is upright, c is inverted
00:07:06.830 --> 00:07:13.509
and when b is acting when b is acting on 110.
So, I am just fixing this, I am not touching
00:07:13.509 --> 00:07:31.550
it and other 2 I will just swap . So, what
I have is therefore, 011 yeah so this is how
00:07:31.550 --> 00:07:51.139
we define the action, but be carefully .
So, exercise for you is that this is actually
00:07:51.139 --> 00:08:02.790
in action
and I guess you remember the definition of
00:08:02.790 --> 00:08:10.162
action. So, if I define the action of clients
4 group action of V4 on this set of 8 elements
00:08:10.162 --> 00:08:20.259
then, it is actually an action ok. Now, the
question is well let us see if number of orbits
00:08:20.259 --> 00:08:29.780
how many orbits are there that, would be something
interesting. So, we estimate the number of
00:08:29.780 --> 00:08:45.810
orbits for this action .
So, I consider say 000 that is all the elements
00:08:45.810 --> 00:09:02.320
are all 3 glasses are inverted . So, I
am looking at orbits of this action. So, in
00:09:02.320 --> 00:09:11.460
all 3 glasses are inverted action of 1 is
again all 3 classes are inverted action of
00:09:11.460 --> 00:09:28.140
a on 000 is 1st position becomes 0 sorry . So,
action of a is 1st position remains unchanged
00:09:28.140 --> 00:09:42.110
and 2 are changed , what about b? When b acts
on 000? What happens you have the middle position
00:09:42.110 --> 00:09:47.960
does not change? And this changes to 1 this
also changes to 1 and. Hence, it happens with
00:09:47.960 --> 00:09:58.030
c what you have last position does not change
and first 2 positions change .
00:09:58.030 --> 00:10:13.600
So, 0 0 0 can move to either of these positions
what about 111 and you have been influence
00:10:13.600 --> 00:10:24.740
of 111 goes to 111, no change what about a
acting on 111 that is simply position of a
00:10:24.740 --> 00:10:36.390
the first position does not change other 2
positions become 0. What about be acting on
00:10:36.390 --> 00:10:51.980
111 is simply this does not change and these
2 things change and c you have this position
00:10:51.980 --> 00:11:08.750
c does not change while other 2 positions
change. So, orbit of 111 has these 4 elements
00:11:08.750 --> 00:11:21.870
fine .
Let us see how many orbits are there this
00:11:21.870 --> 00:11:53.311
action so average number of fixed points . So,
I pick 1, so I pick element of G and number
00:11:53.311 --> 00:12:07.570
of fixed points . So, I take identity identity
fixes everything right so I am using the fact
00:12:07.570 --> 00:12:13.860
that number of orbits is equal to average
number of fixed points as I have explained.
00:12:13.860 --> 00:12:24.260
In previous lectures, what if I pick a how
many elements are fixed?
00:12:24.260 --> 00:12:35.131
So, let us see if a acts on anything it is
not going to be fixed right because other
00:12:35.131 --> 00:12:46.740
2 positions will change. So, number of fixed
points is 0 same is too with b and same is
00:12:46.740 --> 00:13:05.631
too with c. Therefore, number of orbits is
1 divided by size of V4 which is 4 and number
00:13:05.631 --> 00:13:10.730
of fixed points you just add them which is
just 2.
00:13:10.730 --> 00:13:19.100
So, this action has 2 orbits and we have already
identified this orbit and nearby identified
00:13:19.100 --> 00:13:30.040
this orbit and that is all this covers all
the elements of X. So, there are 2 orbits
00:13:30.040 --> 00:13:41.410
these 4 elements are in 1 orbit these 4 elements
are in 1 orbit and therefore, orbit of 0 0
00:13:41.410 --> 00:13:52.890
0 is not same as orbit of 111 .
Therefore, by means of this action therefore,
00:13:52.890 --> 00:14:01.580
by the rules of this game we cannot change
position then all 3 cups are inverted your
00:14:01.580 --> 00:14:09.820
position where all 3 cups are upright. So,
that is very interesting application of the
00:14:09.820 --> 00:14:16.080
group actions the same thing the same problem
I could have We would have understood
00:14:16.080 --> 00:14:24.440
in much simpler terms not even in terms of
group actions, but using the concept of parity.
00:14:24.440 --> 00:14:39.490
So, another explanation to this would have
been using parity so the notion of parity
00:14:39.490 --> 00:14:45.270
something that we are going to learn . So,
let us see in this case what would parity
00:14:45.270 --> 00:15:07.620
mean? So, here to each state I can assign
parity in the following sense so suppose these
00:15:07.620 --> 00:15:15.020
these are 3 positions for the 3 cups abcs
this is inverted. So, this is the notation
00:15:15.020 --> 00:15:33.830
inverted this is notation for upright .
So, whenever I have this down I say one when
00:15:33.830 --> 00:15:53.520
I have upright I say say minus 1. So, X is
a set of all configurations so size of X is
00:15:53.520 --> 00:16:16.570
8 and this map goes parity maps goes from
X to say 1 minus 1. And what it is suppose?
00:16:16.570 --> 00:16:23.750
I take this particular thing. So, this is
a inverting I am doing 1 1 and this is minus
00:16:23.750 --> 00:16:31.560
1 this is the product of these 3 1 into minus
1 to 1 which is minus 1.
00:16:31.560 --> 00:16:43.770
So, to this state I I assign the parity of
minus 1 some other state
00:16:43.770 --> 00:17:00.140
I have minus 1 minus 1 1. So, the product
is 1 ok so here if you check . Here, if you
00:17:00.140 --> 00:17:14.439
observe this has parity minus 1 while this
has parity 1 1 into 1 into 1 and this is minus
00:17:14.439 --> 00:17:20.410
1 into minus 1 minus 1 parity is minus 1.
So, parities are different and interesting
00:17:20.410 --> 00:17:48.620
thing is that the process of playing this
game parity does not change that is the thing
00:17:48.620 --> 00:18:03.120
. Why? Because suppose you have this state.
So, you have 1 minus 1 1 so we have minus
00:18:03.120 --> 00:18:13.850
1 after that, whatever you do you are actually
doing minus. You are changing the position
00:18:13.850 --> 00:18:18.680
of 2 you are changing the configuration of
2. So, we are actually multiplying with minus
00:18:18.680 --> 00:18:23.400
1 square minus 1 squared is just 1.
So, we are not changing the parity in the
00:18:23.400 --> 00:18:31.360
process and since the parity of this is different
from parity of this this parity is minus 1
00:18:31.360 --> 00:18:39.720
here parity is 1. So, we can easily conclude
that you cannot obtain from this position
00:18:39.720 --> 00:18:44.550
all inverted positions to all upright position
so same question.
00:18:44.550 --> 00:18:52.890
Therefore, had 2 different answers 1 in terms
of parity and 1 in terms of group actions.
00:18:52.890 --> 00:19:08.220
And, interesting thing is that we we can
actually use groups to define various notions
00:19:08.220 --> 00:19:32.270
of parity . As, I was saying in the mock in
the previous lecture the signature the notion
00:19:32.270 --> 00:19:38.470
of signature in Sn that is 1 some kind of
parity.
00:19:38.470 --> 00:19:54.880
So, I am going to use that parity and this
kind of parity Z more 2 parity this kind of
00:19:54.880 --> 00:20:02.810
parity to solve for you some other puzzle
and somewhere permutations are there groups
00:20:02.810 --> 00:20:08.340
are there.
So, today we saw how number of orbits
00:20:08.340 --> 00:20:16.430
how calculation of number of orbits could
be useful for some puzzle. Inverted glasses
00:20:16.430 --> 00:20:21.540
puzzle we understood we understood it through
group actions. We calculated orbits the 2
00:20:21.540 --> 00:20:27.090
orbits we explicitly could tell that they
are 2 distinct orbits. Therefore, you cannot
00:20:27.090 --> 00:20:36.060
move from 1 from 1 configuration in this orbit
to other configuration other orbit . There
00:20:36.060 --> 00:20:41.670
is a some some there is few more puzzles that
we are going to discuss.
00:20:41.670 --> 00:20:47.900
So, here is some here is a puzzle which
has to do with parity and then we shall use
00:20:47.900 --> 00:20:59.290
groups to assign parity. So, consider this
so I have this square the tiles 16 tiles
00:20:59.290 --> 00:21:10.480
1 corner is removed, here is a similar set
similar set of tiles the only thing is that,
00:21:10.480 --> 00:21:17.040
the 2 corners which have been removed from
this and as a very simple question. Extremely,
00:21:17.040 --> 00:21:24.130
simple question is I am I am given these
kind of tiles rectangular tiles and the point
00:21:24.130 --> 00:21:31.860
is can I tile up these things.
So, here there are 15 here there are 14 can
00:21:31.860 --> 00:21:42.820
I tell these things using these kind of rectangular
tiles. So, rectangular tile tiles be used
00:21:42.820 --> 00:21:56.570
to obtain this shape and this shape, what
would be your answer it is difficult as you
00:21:56.570 --> 00:22:02.390
can easily observe this has odd number of
tiles 15 is odd.
00:22:02.390 --> 00:22:12.520
So, suddenly you cannot tiled up this using
this these are 2. So, you are using some odd
00:22:12.520 --> 00:22:23.370
what about this
does it always mean that if the number of
00:22:23.370 --> 00:22:29.180
tiles which are here they are even. And this
is an even number you can always tiled in
00:22:29.180 --> 00:22:39.170
this fashion when there is not here application
, but using parity we could at least cross
00:22:39.170 --> 00:22:46.490
this this possibility we could cross right.
So, the various puzzles actually key word
00:22:46.490 --> 00:23:01.650
is parity, where it is quite important a keyword
in puzzles . So, what is parity? So you
00:23:01.650 --> 00:23:09.100
take actually all a priori possible configurations
of a puzzle or all possible situations. You
00:23:09.100 --> 00:23:18.090
take and then you assign each of those configurations
a number it could be 0 comma 1 one of these
00:23:18.090 --> 00:23:23.810
numbers either 0 or 1, it could be minus 1
1 could be color say red and blue it could
00:23:23.810 --> 00:23:29.850
be .
So, what resolved in that previous situation,
00:23:29.850 --> 00:23:37.780
the if the case it was this notion of parity,
which was just take number of squares in the
00:23:37.780 --> 00:23:44.710
configuration. So, with this configuration
number of squares is 15 mod 2 so 15 mod 2
00:23:44.710 --> 00:23:50.130
is what resolved even and odd right that was
essentially parity.
00:23:50.130 --> 00:24:04.640
So, even may be represent by 0 odd maybe represent
by 1 But this care case could not be resolved
00:24:04.640 --> 00:24:19.250
using the notion of parity . What is interesting?
Is that when you have some configuration
00:24:19.250 --> 00:24:26.280
when you have some puzzles it is interesting
to see if while that puzzle is being played.
00:24:26.280 --> 00:24:34.980
While that game is being played something
remains unchanged . For example, in the case
00:24:34.980 --> 00:24:41.790
of 3 glasses the parity remained unchanged.
So, parity was an invariant so an invariant
00:24:41.790 --> 00:24:49.860
can take values in any set quite often the
interesting situations are when this set is
00:24:49.860 --> 00:25:00.690
actually a group . So, as I said invariant
is expected to be constant over the subset
00:25:00.690 --> 00:25:06.790
of possible configurations.
So, if it is if a game is being played so
00:25:06.790 --> 00:25:13.800
all the possible all the plausible configurations
are arriving and it is invariant. So, certain
00:25:13.800 --> 00:25:18.340
thing is constrained some parity is constrained.
So, over all those plausible configurations
00:25:18.340 --> 00:25:35.990
then variance is constant and just being
constant does not mean that your plausible
00:25:35.990 --> 00:25:40.380
configuration is actually there is actually
a reality.
00:25:40.380 --> 00:25:48.410
So, we are going to understand all these things
through an example. So, in the case where
00:25:48.410 --> 00:25:57.550
2 corners were removed, what can we do? We
can use colors and I am going to mathematically
00:25:57.550 --> 00:26:07.870
express that . So, rather than seeing it like
this, I could have seen it like this. And
00:26:07.870 --> 00:26:12.880
when corners are removed this corner is gone
and when this corner is gone.
00:26:12.880 --> 00:26:20.320
If I want to tile it with tiles like this
then the number of yellow tiles should
00:26:20.320 --> 00:26:26.270
be same as number of red tiles, but here I
have removed both tiles which are red. So,
00:26:26.270 --> 00:26:36.540
number of yellow tiles is 8 while number of
red tiles is 6 so it is very clear that if
00:26:36.540 --> 00:26:45.970
I want to use these tiles to completely cover
this knocked off thing with 14 squares.
00:26:45.970 --> 00:26:52.890
I cannot because number of red tiles is not
same as number of yellow tiles all this I
00:26:52.890 --> 00:27:01.930
would say in terms of in terms of parity,
in terms of some invariant .
00:27:01.930 --> 00:27:08.900
So, using the concept of color yellow and
red this using the concept of parity I have
00:27:08.900 --> 00:27:18.960
concluded that this is not plausible. So,
I cannot cover this, I cannot do this using
00:27:18.960 --> 00:27:28.440
these kind of tiles it is impossible . What
was the invariant in the situation? What was
00:27:28.440 --> 00:27:34.480
the parity in the situation? So, all this
colors all the all these colors which came
00:27:34.480 --> 00:27:41.110
to resolve this problem I am going to express
that through this expression.
00:27:41.110 --> 00:27:50.900
So, tile ij is colored if it is it is colored
yellow if i plus j is congruent to 0 mod 2.
00:27:50.900 --> 00:28:03.370
So, i plus j is having value 0 in the group
Z 2 otherwise it is colored red. And what
00:28:03.370 --> 00:28:13.050
is configuration x configuration x is tiles
with these coordinates i1 j1 it is 1 1 tile
00:28:13.050 --> 00:28:20.360
other tile with cognates i 2 j 2 they have
been removed from the 4 cross 4 that chess
00:28:20.360 --> 00:28:32.570
board . And then if you define your number
the invariant associated to be i 1 plus j
00:28:32.570 --> 00:28:40.160
1 plus i 2 plus j 2 mod 2. And that resolves
the problem and the observation would be that
00:28:40.160 --> 00:28:48.480
if f x is 0 then that particular configuration
x is not plausible.
00:28:48.480 --> 00:28:58.120
So, for example, if I knock it out knock it
out this this particular one then they are
00:28:58.120 --> 00:29:03.620
of the different color. So, after removing
exactly 2 tiles of different color what you
00:29:03.620 --> 00:29:11.550
would have? Is that the number the the invariant
with that I have defined like this is actually
00:29:11.550 --> 00:29:20.460
one. So, then question is what configurations
can be constructed from those rectangle then
00:29:20.460 --> 00:29:26.770
that rectangle that I have 1 1 by 2 tiles.
Those, smaller rectangles and answer is
00:29:26.770 --> 00:29:37.750
all it is not very difficult are some graphs
which are required to understand this part
00:29:37.750 --> 00:29:45.890
I am going to do it here.
So, basically what I want to say is that the
00:29:45.890 --> 00:29:51.600
concept of invariants and some mod 2 invariants
can be used to resolve certain puzzles and
00:29:51.600 --> 00:29:59.610
here your function is lying in the group Z
2. So, we shall have some more interesting
00:29:59.610 --> 00:30:07.600
some quite interesting puzzles later on so
I hope you enjoyed all this. So, in coming
00:30:07.600 --> 00:30:15.390
lectures we will try to see more applications
of groups we will see 15 puzzle we will
00:30:15.390 --> 00:30:21.690
see Rubik's cube. And you will see how we
can understand ? How we can use our understanding
00:30:21.690 --> 00:30:27.380
of group theory to resolve the issue the
resolve the problems which arise in those
00:30:27.380 --> 00:30:29.899
puzzles.
Thank you.