[MUSIC] Well, you can easily see that this solution is indeed wrong. Why is it wrong? Because well, the first way to check it is that this answer is not always integer. That if say if n is not divisible by p, then you won't get an integer number as the answer to your combinatorial problem. And if you get a non-integer as the number of ways of doing something, that means that most probably you have done a mistake somewhere. So what is wrong in this reasoning? Well, the first mistake is that if, the first in demand mistake is that if we have a merry-go-round. And it was splitted in two different places. Sometimes we get the same train. For instance, this will happen if all the carriages of our merry-go-round have the same color. This was allowed and this means that wherever you cut it you will get the same train. This merry-go-round will give us only one color trains, not p then. So there is only one train. Okay, and what happens now if there are different colors occurring the coloring of our merry-go-round? So my claim is that If there are different colors occurring here, then we'll get exactly p different trains out of each merry-go-round. Provided that the number p is prime. So our naive reasoning will work in our case if not all the carriages have the same color. But if. There are. At least. Two columns involved. This solution works. What is it so? Why can't we get the same train in p different ways from this merry-go-round? The answer is as follows, that if you rotate this merry-go-round by an arbitrary number of carriages, it will coincide with itself. So each pink carriage will go to the pink one. So this means that if you cut this merry-go-round and two orbital places you will still get the same train of the same color. And if you do the same with the painting which has different colors, I claim that you will get exactly p different trains provided that p is prime. So my claim is that if p is prime, that then colored merry-go-round cannot be mapped into itself by a rotation to an arbitrary non-zero number of carriages. Let us prove this. Suppose that we have a merry go round and let's take a carriage and suppose that we have rotated it by some angle. And it is mapped to itself. This means that well, suppose that say in this example we rotated by two. This means that this blue carriage will go to this carriage. And if the rotated merry-go-round coincides with the original one, this one should also be blue. Okay and what happens with this carriage as you rotate it by two again? It must coincide with this one. Okay, and so these two also have the same car and and the same is true with this and this one. And finally the last carriage is obtained from the previous one by rotating by two so we get that all carriages have the same have the same color. So if a merry-go-round. Goes to. Itself. After some nontrivial rotation. Then, all carriages have the same color. Note that this not true if, so out of this merry-go-round we get exactly, well, if not all carriages have the same color, we get exactly p different trains. And note that this is not true if p is not prime, because say if you have a, here's an example. If you have a merry-go-round with four carriages, four is not prime. And they are called like this, white, black, white, black. Then there are only two different cranes which you can get from this merry-go-round. Here they are. White, black, white, black and black, white, black, white. So you have two of them, not four. And if p is prime then we get exactly p different trains. So. If our merry-go-round has carriages of different colors, then you can compute the number of such merry-go-rounds. And it is the number of cranes divided by p. And what's the number of trains which have different cars? Which do not have the same color of all carriages. So it is n to the power of p, which is the total number of trains, minus the number of trains of the same color. So minus n. For each color, there is only one train where all carriages have this given color. So this is the number of trains where at least two carriages have different colors. And you divided by p. And this is the number of merry-go-rounds with carriage of a different color and to get the total number of merry-go-rounds you need to add single colored ones. So this is the correct answer. The total number of merry-go-rounds. What is the most suprising in this answer? Again, this is a combinatorial program so the answer should be an integer number. And if you look at this expression, it is absolutely not obvious that this thing is integer. So why is this thing integer? So we have obtained the following result. Theorem. N to the power of p minus n is divisible by p. And this is called Fermat's little theorem. Probably, you have seen this theorem in some algebra or number theory course. And we have provided a combinatorial proof of this fact just by showing that this number n to the power of p minus n is integer because it counts objects in certain finances. [MUSIC]