Category Archives: Quiz

Kings and Slaves

Since years I ask people sometimes the Kings-Slaves Question that came to my mind some years ago. The funny thing about it, is that I get the most different and unexpected explanations for the respective choice. The dilemma has its own page in my site, you can click the link from the navigation bar above.

A quiz for bike riders

After riding the bike many days on the same roads, I came to the following interesting exercise: find a speed, such that you can reach your destination with this speed without having to stop at a red light. Of course we assume, that we always stop at red light.

So the exercise is the following. Consider a finite number of traffic lights, a_0, \ldots,a_n, and suppose that the bike rider starts when a_0 becomes green. Then let T_1,\ldots,T_n be the times for which the respective lights are green, and F_1,\ldots,F_n be the times for which the lights are red. Further, let d_1,\ldots,d_n be the distances between the lights, and suppose that we know at t = 0 the remaining green or red time for every light. Let these times be R_1,\ldots,R_n with positive times for remaing green and negative for remaining red time. Determine the set of all possible constant speeds (also unrealistic) for which the rider can pass through without having to stop.


P.S. (R_1,\ldots,R_n) could be any n-tuple from \{(x_1,\ldots,x_n)|x_i \in [-F_i,T_i] \}

P.S.2 He he, it is easy to find some trivial funny unrealistic solutions. But we want all solutions!

Quiz: How many 12-tone rows do exist?

The composer Arnold Schönberg introduced in the 3rd decade of the 20th century the composition with 12-tone rows. Many composers after him used the 12-tone system, each one in his own way: Anton Webern, Alban Berg, Igor Stravinsky are some of the most prominent.

We will denote a 12-tone row as a permutation of the set S={0,...9,A,B} (we will use A for 10 and B for 11). But each 12-tone row has 12 transpositions (S+i, i=0,...11) and 4 forms: the original form, the inversion (the permutation with the complementary intervals), the retrograde form, and the retrograde inversion. Each form has 12 transpositions, thus we have 48 permutations. For example, the main row that uses Berg in opera Lulu is: 4 8 9 6 B 1 A 0 3 2 7 5. All 12-tone-permutations of it are listed in the following table:

Prime Retrograde Inversion Retrograde Inversion
04527968BA31 13AB86972540 087A5364129B B9214635A780
15638A790B42 24B097A83651 198B647523A0 0A325746B891
26749B8A1053 3501A8B94762 2A90758634B1 1B43685709A2
3785A09B2164 4612B90A5873 3BA186974502 205479681AB3
4896B1A03275 57230A1B6984 40B297A85613 31658A792B04
59A702B14386 68341B207A95 5103A8B96724 42769B8A3015
6AB813025497 794520318BA6 6214B90A7835 5387A09B4126
7B09241365A8 8A56314290B7 73250A1B8946 6498B1A05237
801A352476B9 9B674253A108 84361B209A57 75A902B16348
912B4635870A A0785364B219 95472031AB68 86BA13027459
A2305746981B B1896475032A A6583142B079 970B2413856A
B3416857A920 029A7586143B B7694253018A A8103524967B

Thus we can code all these 48 permutations as (0 4 5 2 7 9 6 8 B A 3 1) and denote the prime forms with Pi (where i is the first element of the Pi-form), the retrogrades of  Pi as Ri, the inversion of Pi as Ii and the retrograde inversions of Pi as RIi, where i=0,...11. Thus all 48 permutations can be coded as one form of the prime one. This is an information compression. These 48 permutations can be used in a 12-tone work, that is based on a 12-tone row (say P4).

But not all rows have 48 permutations. For some of them the retrograde form has the same interval sequence as the prime one. And for some, the retrograde inversion has the same interval sequence as the prime one. These rows have only 24 permutations.

In some musicological books I read, that all possible rows are 12!. This is not correct, because —as we saw above— we can reduce 48 permutations (or 24, in the case of the symmetrical rows) into just 1 row. And here comes the first question: how many rows are there? If we reduce them sufficiently, then we could index them, which would be very convienient for the musicological reference to the rows.

The second question is a bit more difficult. Some composers use the permutations in rotated form. Thus we could reduce the indexing further. E.g. we could denote (4 5 2 7 9 6 8 B A 3 1 0) as the 1st rotation of (0 4 5 2 7 9 6 8 B A 3 1) and not as a different row. But there are rows, that have symmetries with reference to rotation. If we respect rotation as well, how many rows do we have?

A combinatorics quiz

Let's consider the connexion between two persons from the mothers' side and count the possibilities to express it. E.g., if the connexion is only 1 generation, then there is only 1 possibility to express it:

  1. the mother.

If the connexion is 2 generations, then there are 2 possibilities to express it:

  1. the mother of the mother
  2. the grandmother.

If the connexion is 3 generations, then there are 4 possibilities to express it:

  1. the mother of the mother of the mother
  2. the grandmother of the mother
  3. the mother of the grandmother
  4. the great-grandmother.

If the connexion is 4 generations, then there are 7 possibilities to express it:

  1. the mother of the mother of the mother of the mother
  2. the mother of the mother of the grandmother
  3. the mother of the grandmother of the mother
  4. the grandmother of the mother of the mother
  5. the grandmother of the grandmother
  6. the mother of the great-grandmother
  7. the great-grandmother of the mother.

Now, if the connexion is 100 generations, how many possibilities are there to express it by using only the words "mother", "grandmother", "great-grandmother", "the" and "of"?

Calculate the same for 1000 generations. Can you have the answer in less than 10 seconds? (10'' of computer calculations)

Here is my answer.


Damn it! I have just guessed an algorithm, that can calculate this in linear time and in less that 1 sec! Can you guess it too? ;o)

Here is my second answer.