WEBVTT
Kind: captions
Language: en
00:00:08.040 --> 00:00:16.480
.
So, as you recall last time what we have done
00:00:16.480 --> 00:00:29.590
was just putting into in the form of permutation
, how all these moves can be written as permutations
00:00:29.590 --> 00:00:40.250
right . So, this was clear to us a top one
and now we are going to see for other phases
00:00:40.250 --> 00:00:47.750
as well. So, for the left one what is happening
. Its quite clear 9 goes to 11, 11 goes to
00:00:47.750 --> 00:00:55.300
16, 16 goes to 14 and then 14 comes back.
So, you have like this and then what happens
00:00:55.300 --> 00:01:08.920
to other one 10 13 15 12 10 10 13 15 12 and
back to 10, what about 1 1 goes to this move,
00:01:08.920 --> 00:01:13.950
so you are moving it . So, this is the thing
and the left one is what you are moving right.
00:01:13.950 --> 00:01:23.220
So, you moving it like this , it from here
the clock wise direction right and when you
00:01:23.220 --> 00:01:30.409
open the cube you realize that what happens
to 1. In this move is 1 goes to 17, 17
00:01:30.409 --> 00:01:39.840
goes to 41 and 41 goes to well the way
cube is packed, this opened cube 41 actually
00:01:39.840 --> 00:01:46.799
goes to 40 .
So, that you have to realize by experimental
00:01:46.799 --> 00:01:54.530
and similarly what happens to 4 4 goes to
20, 20 goes to 44 and 44 actually goes to
00:01:54.530 --> 00:02:04.880
7 again the way cube is packed and then 37
comes back to 4 and similarly 6 6 goes
00:02:04.880 --> 00:02:25.590
to 22, 22 goes to 46 and 46 goes to 35. So,
we can write all this f is like this 17, 19,
00:02:25.590 --> 00:02:43.999
24, 22 back to 17 and then 18, 21, 23, 20
and back to 18 and it also affects other sides.
00:02:43.999 --> 00:02:53.239
So, for that this is being given 6 goes to
25. So, this 6 goes to and we are moving like
00:02:53.239 --> 00:03:08.359
this, actually goes to 25 and 25 goes to 43,
43 goes to 16 and then it comes back to
00:03:08.359 --> 00:03:12.590
6.
So, you have to identify all this. Similarly
00:03:12.590 --> 00:03:22.659
for write you have this or back you have this.
This is back and for bottom also you have
00:03:22.659 --> 00:03:30.040
this yeah. So, this is what Rubik's cube is
made of, Rubik's group is made of all these
00:03:30.040 --> 00:03:35.309
basic permutations and they have written all
these basic permutations. So, if I do the
00:03:35.309 --> 00:03:42.530
left thing twice, when I move the left face
twice I will do this square of this permutation
00:03:42.530 --> 00:03:46.239
right .
So, now what we can do is, we can try to write
00:03:46.239 --> 00:03:53.999
it as a group. So, I want to group which is
generated by these elements. So, I want to,
00:03:53.999 --> 00:04:00.029
I want a gap software to remember a group
and then group is generated by. These are
00:04:00.029 --> 00:04:08.069
the basic moves right, this is the moves we
know our 1 3 8 6 2 5 7 4, these 1 3 8 6 2
00:04:08.069 --> 00:04:19.650
5 7 4 and so on. So, I just cut and paste
all these in the software gap software .
00:04:19.650 --> 00:04:47.340
So, I have put all these, and I enter what
it says is that I have created a permutation
00:04:47.340 --> 00:04:53.100
group with 6 generators and you recall what
are those 6 generators are, repressively T
00:04:53.100 --> 00:05:02.450
L F R Ba and B all these things. Those are
6 generators of the Rubik's cube.
00:05:02.450 --> 00:05:11.100
What the first thing you would do. Well we
will like to determine the size of this , how
00:05:11.100 --> 00:05:33.410
much you think would it be millions, trillions,
let us see , oh I gave the wrong name this
00:05:33.410 --> 00:05:45.650
is Rubik's grp and this was the size grid
, its beyond billions beyond trillions. So,
00:05:45.650 --> 00:05:58.900
how to rectify this ? I will try to write
it in the readable form. So, . So, factors
00:05:58.900 --> 00:06:07.960
of this and I write it collected. I hope you
remember last time I mention this command
00:06:07.960 --> 00:06:11.430
.
So, this is the number 2 to the power 27 times
00:06:11.430 --> 00:06:19.580
3 to the 14 times 5 to the power 3 and 7 to
the power 2 and 11, multiplied by 11, its
00:06:19.580 --> 00:06:29.890
a huge number huge number. So, I would show
you and just in I do not .
00:06:29.890 --> 00:06:36.640
So, this is what we have got right, size of
Rubik's group group is this much 4 3 2 5 and
00:06:36.640 --> 00:06:45.300
this huge number the size of the Rubik's group
I will mention interesting quotation from
00:06:45.300 --> 00:06:56.180
this book called Innumeracy Mathematical illiteracy
and its consequences, quite interesting book
00:06:56.180 --> 00:07:06.830
by John Allen Poulos and it quotes and
this is the beginning days when Rubik's cube
00:07:06.830 --> 00:07:15.360
was made with this Toy Company claimed that
there were more than 3 billion possible states
00:07:15.360 --> 00:07:21.110
the Cubik's cube could attain.
They claim with a beginning there are around
00:07:21.110 --> 00:07:26.460
3 millions different states. So, this is 1
state ; that is 1 state, that is 1 state,
00:07:26.460 --> 00:07:32.990
exactly 1 of the states is solid states ; so,
the claim that it has more than 3 billion
00:07:32.990 --> 00:07:39.930
states; however, calculations show.
So, the calculation that we did just now using
00:07:39.930 --> 00:07:47.110
gap, it show that there are more than 4 into
10 to the power 19 right. So, this something
00:07:47.110 --> 00:08:01.370
like 4.325 into 10 to the power 19 , the more
than this possible states, 4 with 19 zeros
00:08:01.370 --> 00:08:08.690
after it and then the gives beautiful analogy;
say this analogous to a sign at the entrance
00:08:08.690 --> 00:08:16.650
of Lincoln Tunnel stating New York population
is more than 6, its analogy. Oh McDonald proudly
00:08:16.650 --> 00:08:21.850
announcing that they have sold, they have
sold more than 120 hamburgers.
00:08:21.850 --> 00:08:29.550
So, this is the the huge in a accuracy, this
is the orders of magnitudes of a inaccuracy
00:08:29.550 --> 00:08:34.270
that was there in the beginning. Anyway let
us come back, let us come back to our gap
00:08:34.270 --> 00:08:42.559
program by realizing that there are so
many of the order of 10 to the power 19 different
00:08:42.559 --> 00:08:48.639
states that Rubik's cube could attain . So,
we have, we have already factorize this, the
00:08:48.639 --> 00:08:52.870
huge numbers, so this is the size and now
is the crucial thing.
00:08:52.870 --> 00:09:02.199
So, we have realized that there are 6 generators
of it . So, how you actually solve? So, first
00:09:02.199 --> 00:09:11.459
I I construct a free group with 6 generators.
So, I just call those generators as t l
00:09:11.459 --> 00:09:18.370
f are e, just because I do not want to use
b twice and I am just using the denomination
00:09:18.370 --> 00:09:30.680
e. So, I am just having free group on these
6 generators. So, let me just do that .
00:09:30.680 --> 00:09:48.939
So, free group on 6 generators what is the
order of it, well free group is infinite just
00:09:48.939 --> 00:10:03.249
for 1 lakhsy order of a f infinity, its a
quite smart ok. So, I have constructed free
00:10:03.249 --> 00:10:12.300
group which is 6 generators, and now I
construct homomorphism from the free
00:10:12.300 --> 00:10:19.300
group two Rubik's group; that is crucial
part. So, free group is something where operations,
00:10:19.300 --> 00:10:25.199
all the symbols are getting multiplied
with themselves freely.
00:10:25.199 --> 00:10:29.809
So, if I do it four times, I know I am going
back to identity position, but in the free
00:10:29.809 --> 00:10:36.029
group anything raised to the power is non
identity, if the original thing is non identity
00:10:36.029 --> 00:10:42.759
. So, there are no relations in a free group.
So, I want use free group to understand this.
00:10:42.759 --> 00:10:48.580
So, for that I will construct a homomorphism
from free groups to Rubik's group and how
00:10:48.580 --> 00:11:02.139
to I do this. Here is command, so I group
homomorphism by images. So, I specify the
00:11:02.139 --> 00:11:07.470
this element goes to that element, this elements
goes to that element like that, I would
00:11:07.470 --> 00:11:13.680
specify the homomorphism . So, let us see
what are the generators of group f and what
00:11:13.680 --> 00:11:21.300
are the generators of group Rubik's cube .
So, first generators of , this is a command
00:11:21.300 --> 00:11:35.430
, I will phase like command here . So, generators
of group f r these, and then generators of
00:11:35.430 --> 00:11:53.300
the group Rubik's group are all these elements
right. So, I will map t to this, t which is
00:11:53.300 --> 00:12:02.679
the element of free group to this . Then I
will wrap l to this and then I will map f
00:12:02.679 --> 00:12:09.019
to this like that, and then I will generate
a homomorphism. Homomorphism is supposed to
00:12:09.019 --> 00:12:15.019
preserve relations, but then there are no
relations here . So, there is no not much
00:12:15.019 --> 00:12:21.029
of the worry .
So, if t goes to this, the t square will be
00:12:21.029 --> 00:12:26.839
going to square of this. So, in that fashion,
I am going to have my homomorphism and that
00:12:26.839 --> 00:12:35.170
homomorphism I can define in gap using this
command; group homomorphism by images and
00:12:35.170 --> 00:12:42.660
I am giving homomorphism from the free group
f to Rubik's group and generators of f which
00:12:42.660 --> 00:12:48.029
are these t l f r e b, they are going to generators
of the Rubik's group, which are precisely
00:12:48.029 --> 00:12:52.480
the basic moves. So, those, those basic moves
are being mapped too ok.
00:12:52.480 --> 00:13:07.129
So, let me define this , copy it . So, this
is phase stage .So, homomorphism is created.
00:13:07.129 --> 00:13:14.249
So, homomorphism this goes to this. So, first
key goes to that and l goes to that like that,
00:13:14.249 --> 00:13:23.490
l is left and f is front and all that.
So, I defined homomorphism ok. So, here
00:13:23.490 --> 00:13:29.379
is a free group, the homomorphism is defined
to the Rubik's group. So, I will not worry
00:13:29.379 --> 00:13:35.839
about relations, because free group is not
having relations and then let, let us just
00:13:35.839 --> 00:13:41.389
arbitrarily picks some element in the Rubik's
group and look at its pre image .
00:13:41.389 --> 00:13:48.470
So, this element I have just written, but
here let us see, let us pick some arbitrary
00:13:48.470 --> 00:14:06.819
element . So, I am taking, say x is a random
element of Rubik's group , some element x
00:14:06.819 --> 00:14:19.749
ok and now what, what do I do? I consider
pre image of the the of that element . So,
00:14:19.749 --> 00:14:27.509
here I just consider pre image of that element
or the some other element, but let me just
00:14:27.509 --> 00:14:42.564
take
So, in case of that I am takes some elements;
00:14:42.564 --> 00:14:53.959
say x , the some element x and the pre image
of a that element in the Rubik's group.
00:14:53.959 --> 00:14:57.790
So, let me explain what I have done so far
00:14:57.790 --> 00:15:11.439
Here is Rubik's group, let me call it the
huge one , let me call it r and I have recognize
00:15:11.439 --> 00:15:24.540
generators of it, top, left, right, front,
back, bottom and then I have define a homomorphism,
00:15:24.540 --> 00:15:40.470
some 6 symbols for this there is no symbol
back I did not want to use b again . So, like
00:15:40.470 --> 00:15:51.379
that I have defined a homomorphism .
And as we would recall, as I am saying this
00:15:51.379 --> 00:16:03.310
suppose, this is called this is being denoted
by hom hom, and hom hom of a b is same as
00:16:03.310 --> 00:16:14.149
hom a hom b . So, for that reason automatically
the t square will mapped to t square like
00:16:14.149 --> 00:16:20.040
that. So, I have define this. And now what
I do? I pick an element here . What is an
00:16:20.040 --> 00:16:24.699
element here? An element here is the state
of the Rubik's cube, some random state of
00:16:24.699 --> 00:16:31.139
the Rubik's cube that random element
So, that is where I had picked random element
00:16:31.139 --> 00:16:37.540
here you remember, this one I have I have
this random element and then I am looking
00:16:37.540 --> 00:16:46.910
at the pre image of this random element. So,
pre image of random element in this . Suppose
00:16:46.910 --> 00:16:53.399
x is random element, its going to be huge,
there is no one single element in f. So,
00:16:53.399 --> 00:16:58.699
this is not 1 1 right. This is after well
in finite group, this is finite group . So,
00:16:58.699 --> 00:17:04.850
the huge sub set of f which is there in
the pre image of x. So, I am just picking
00:17:04.850 --> 00:17:10.020
one representative from it. So, that representative
will; of course, mapped to x. Anything that
00:17:10.020 --> 00:17:14.000
I have take in the x at is going to mapped
to x that is in the pre image .
00:17:14.000 --> 00:17:23.910
So, I take a representative in the pre image
and that is a representative, this just is
00:17:23.910 --> 00:17:31.780
f into r into t into r in inverse into f inverse
into l inverse and e inverse and so on like
00:17:31.780 --> 00:17:40.380
that, there is pre there is representative
in the pre image . So, I do that and how much
00:17:40.380 --> 00:17:47.160
is the length of that. Well let us see, length
is also a command , length of whatever is
00:17:47.160 --> 00:17:56.860
the output from previous command, last is
k 6 98 ; In some earlier program that I had
00:17:56.860 --> 00:18:03.050
written , that I had done calculation form,
it was 77 ok.
00:18:03.050 --> 00:18:14.400
Now, I have already asked gap to choose
a random element that is what we did the calculation
00:18:14.400 --> 00:18:21.820
and we can actually look at the image of this
. So, what you are x we can look at the image
00:18:21.820 --> 00:18:32.980
of that x , not pre , the is x , that is the
image .
00:18:32.980 --> 00:19:19.240
So, let me just see . So, pre image is this
one, and what we do with this pre image, we
00:19:19.240 --> 00:19:32.370
just that all our moves . So, we get that
x is . So, our x has some, this random
00:19:32.370 --> 00:19:39.920
element x is certain combination; say I am
just for illustration I am taking say pre
00:19:39.920 --> 00:19:54.690
image of x to be, say just for illustration;
t times l inverse r f inverse e b inverse
00:19:54.690 --> 00:20:00.500
r l something.
So, that is x right, that is the state. So,
00:20:00.500 --> 00:20:08.600
in order to get the identity element what
do I do? I just start with from here other
00:20:08.600 --> 00:20:21.540
side right, l inverse r inverse b e inverse
f r inverse l t . So, when I apply this move
00:20:21.540 --> 00:20:28.570
then I will be solving my cube .
So, this this tells you how I have obtain
00:20:28.570 --> 00:20:33.630
this state from the identity right, how I
have reached this state from identity , but
00:20:33.630 --> 00:20:39.870
that is reading in the free group, but
if I do it in the reverse direction in the
00:20:39.870 --> 00:20:47.320
free group, what it does is actually solves
the cube for me. So, I hope things are
00:20:47.320 --> 00:20:54.540
clear to you. So, if certain identity position
is there , I am is unscrambling the, I am
00:20:54.540 --> 00:20:59.780
scrambling the cube and unscrambling is precisely
taking inverse in the free group in that is
00:20:59.780 --> 00:21:02.870
what I am doing.
So, although this might not be the most efficient
00:21:02.870 --> 00:21:10.080
way, because the pre image that I have paid,
is just one of the pre images. I am not taking
00:21:10.080 --> 00:21:14.810
any , I am not taking the pre image which
is shortest in length. So, that is the drawback,
00:21:14.810 --> 00:21:24.570
but nevertheless through all this we can understand
that , we can store first of all the Rubik's
00:21:24.570 --> 00:21:33.160
cube in gap and then we can solve using gap
using the idea of homomorphisms, at free groups
00:21:33.160 --> 00:21:38.310
are playing important role. And as you can
see here all these moves, the sequence of
00:21:38.310 --> 00:21:51.570
all these moves is nothing, but a word right.
This expression as you recall is a word , word
00:21:51.570 --> 00:21:59.030
in the free group. So, that is all .
So, everything is a origin of free group,
00:21:59.030 --> 00:22:03.840
all these moves that are doing. You should
try to realize them as elements in a free
00:22:03.840 --> 00:22:10.720
group right. So, we can you, we can
use this these simple ideas by constructing
00:22:10.720 --> 00:22:16.730
Rubik's cube group and then by considering
homomorphisms and then just taking the inverse
00:22:16.730 --> 00:22:25.710
image of any random , inverse image of any
random element and then taking a the, the
00:22:25.710 --> 00:22:32.351
inverse of that word and that is, that is
it that is precisely one can easily solve
00:22:32.351 --> 00:22:36.700
Rubik's cube although I am not caving the
x going to be efficient way, because the pre
00:22:36.700 --> 00:22:43.490
image which is going to come is not the
shortest one, is not of the shortest length,
00:22:43.490 --> 00:22:49.790
that is a small drawback
Similarly what we did for 2 1 by, what we
00:22:49.790 --> 00:22:56.040
are did for 3 by 3 cube. We can also do
it for 2 by 2 cube and this time situation
00:22:56.040 --> 00:23:04.320
is much simpler and the group which is there
. Earlier the group was s 48 and this time
00:23:04.320 --> 00:23:13.880
everything is moving the 6 faces. So, 4 into
6 minus 0. So, as 24 is going to be the group
00:23:13.880 --> 00:23:18.850
in which all the permutations are going to
lie , it would be interesting exercise for
00:23:18.850 --> 00:23:25.740
you to find out how much is the size of the
Rubik's group for 2 by 2, and it wonderful
00:23:25.740 --> 00:23:35.300
if some of you those who can easily download
cap software then those people can solve
00:23:35.300 --> 00:23:44.070
Rubik's cube using this method .
So, now, I hope you understand why we introduced
00:23:44.070 --> 00:23:52.430
free groups and homomorphism, the purpose
was to understand how gaps stores all these
00:23:52.430 --> 00:23:58.800
things and how we can use those things to
solve cube, to Rubik's cube in this case.
00:23:58.800 --> 00:24:06.830
So, its permutation puzzle. So, all the permutations
puzzle, which which concern scrambling
00:24:06.830 --> 00:24:15.390
and unscrambling something, they can be understood
using these ideas. So, I hope you could follow,
00:24:15.390 --> 00:24:20.990
I hope you could enjoy. If there is any difficulty
you can always contact us.
00:24:20.990 --> 00:24:22.530
Thank you.