Dutch mathematician Debruin solved this problem.
B(k, n) is a cyclic sequence consisting of k elements. All k elements of length n appear in their subsequences (in the form of rings) and only once.
For example:
Sequence 0001011belongs to b (2,3).
All subsequences of length 3 of 000 10 1 1 are 000,001,0 10, 01.
The length of Debruin sequence is
The n power of k is 2, and the 3 power is 8.
After introducing the basic formulas and feelings, it is estimated that many students, like me, are puzzled. But it doesn't matter. The author will take his time and see if he can understand it in the end.
You can Google the Debruin sequence (hereinafter referred to as DB), which is probably related to a magic trick. However, the author is also a magic lover, and he is very interested at once. This is the moment to witness the miracle (there should be background music and brain tonic).
1 First, prepare a deck of playing cards and invite five people to cooperate. (Why five people, because the fifth power of 2 equals 32), check that the playing cards are four numbers with different colors from 1 to 8.
2. Disrupt the playing cards and let five people take them from them in turn. At this time, you can say, I already know what the cards in your hand are. (Actually, you don't know. )
3. There is another key step, that is, let the black (spades, clubs) among the five raise their hands. Only in this way will you really know what their cards are.
The answer is here:
In fact, we can regard the 32 cards of five people as a DB sequence.
In other words, B (2,5) has 32 binary strings arranged and combined. The length of each string is 5.
For example, the first digit on the left of 00000 is 0 for color (black and red), the second digit on the left is (suit), and the last three digits are numbers, so 000 represents 8.
Then compare figure 2. And the order in which those who hold black cards raise their hands, you can tell what each person's cards are.
Take B (2,3) as an example. The different binary strings with the length of 3 are 000,001,01,01,165438 respectively.
As shown in the figure, starting from 000,
It will eventually return to 000, and the 8-bit binary string obtained is 000101or 00011.
If there is anything wrong, welcome to discuss.