Combinatorics and board games

It so happened that over the past six months I managed to get acquainted with several simple (in the sense of the rules) and somewhat similar board games. The first in this row was Set, then Lamb, and in the summer we played Dobble. I must say right away that all of these games are very exciting, however, this post will be discussed, of course, not about that. The fact is that after some time (in other words, having played enough), I was interested in the ideas that underlie these games, and which turned out to be closely connected precisely with combinatorics. In this post, we will talk about the simplest (in my opinion) game - “Lamb”, which, incidentally, in the original version has a more harmonious name “Geistesblitz” (German: illumination).



Rules of the game


So what is the game. There are 5 objects, each of which, relatively speaking, is characterized by shape and color (i.e., two categories) - a white drum, a red chair, a blue book, a green bottle and a gray mouse.



In addition, there are a number of cards, each of which depicts two objects having a different shape and a different color (but from the above shapes and colors). Some cards contain items that exactly match the real items. On any card in at least one item, the color does not match the shape (for example, a red bottle).



The goal of the game is that for a given card, as soon as possible, identify an object that a) is either present in the correct form on the card (the shape and color match), b) or is completely absent (there is neither the form of this object on the card, nor its colors).



In the first example, we have a white drum, and we have to grab it; in the second example, our choice is a bottle, because there is no bottle (as a shape) on the card and there is no green color (it is easy to verify that in this case the bottle is the only option, as separate categories of all remaining items are present on the card).

Actually, all the rules. The game itself is designed for several players, each one plays for itself, the goal is to collect as many cards as possible (whoever grabbed the right item first, that’s the card). Attention: do not play with people with long nails, it is possible to get stab wounds!

Number of cards


The first question that interested me was how many different cards are possible in this game. Pure combinatorics! What is nice, this problem is solved quite easily. To begin with, we note that we have two types of cards, let's call them correct (they have the right item) and wrong ( there is no necessary item on such cards). We calculate separately the number of those and others.

Let's start with the right ones. The first item on the correct card can be selected in five ways (out of the five available items). The second item is chosen more cunningly - first we choose its shape (four options, one shape is already occupied by the first item), then color (three options, one color is occupied by the first item, the second is occupied by the item from which we took the form in the second step). Thus, according to the rule of the product , we get the total number of correct cards 5 * 4 * 3 = 60.

Wrong cards are considered similarly. First, select the shape of the first item (5 options), then its color (4 options). Then select the shape of the second item (3 options) and its color (2 options). Just one unchallenged item remains - the purpose of this card. We apply the product rule, we get 5 * 4 * 3 * 2 = 120 options. But this is the wrong answer - the set of items on the card is disordered , and we calculated the number of ordered sets. To get the right answer, you need to divide 120 by 2 - the number of permutations of two elements (card “red bottle and white chair” = card “white chair and red bottle”). Thus, we get 120/2 = 60 wrong cards.

Summarize (i.e. apply sum rule ) and we get the answer: 120 cards for the game. We count cards in the game - 60 pieces. Either an error in the calculations, or a shortage. A simple investigation revealed the fact of shortage - for each of the five items, there are six correct and six wrong cards, and there should be 12 and 12. Moreover, no logic was found in the selection of cards (most likely a random choice).

Generalization


We reformulate the problem slightly. There are N objects, each of which is described by k categories, and there are Q cards on each of which n objects are depicted (in the case considered above, N = 5, k = 2, n = 2 and Q = 120). There are limitations - cards can be correct (in the above sense) and incorrect. In any case, on each card, none of the kN possible signs is repeated (for example, all colors are different and all forms are different). In addition, each item is either completely depicted on the card, or there is no more than one attribute from it: for example, in “Drum” there is no card with a white bottle and a red drum (two signs from one object), because There are two choices for such a card - a gray mouse or a blue book. The only and natural question который возникает в такой обобщенной постановке — какова связь между переменными N, k, n и Q?

First, it’s easy to establish how N, k and n are related. Consider the wrong cards. Each such card contains n objects, which means there are exactly kn signs on it that define the kn objects (all signs are different, no two belong to the same object). Since such a card must correspond to a single item that is not included in it, we get the required number of items kn + 1. Note that this number also allows you to make the correct cards (on each correct card 1+ (n-1) k items are present in one form or another). Thus, N = kn + 1. It is easy to verify that the formula is valid for the case n = k = 2 and N = 5 considered above. Imagine the found dependence in the form of a table (the cell corresponding to the game “Lamb” is highlighted in red):



What do these numbers mean? Suppose we want to create an extended (super-complex) version of the game, in which on each card there will be n = 5 items, and each item will be described by k = 5 categories. We get N = 26. This means that for each category it will be necessary to come up with 26 of its values ​​(attributes). Those. if the category is color, then 26 colors that are well different from each other must be identified. This is not an easy task ... Therefore, possible game extensions are most likely limited to the area near the upper left corner of the table. By the way, the seemingly trivial cases of n = 1 or k = 1 also have the right to life (although, most likely, a good reaction will be the main thing in these cases).

We now calculate the number of Q cards in the extended (parameterized) version of the game. Using the above technique, we find the number of correct cards N! / K! / (N-1)! and the number of wrong cards N! / n !, adding and simplifying, we get the result . br@0/>
.

The formula works for n = k = 2, and has also been tested for lower values ​​of these parameters. True, in the case n = k = 1, it is slightly lying, because in this case, the correct card for one item coincides with the wrong card for another item (that is, any choice will be winning), so the result should be divided by 2. In all other cases, such collisions do not happen. For the case n = k = 3, the formula gives the number Q = 907200. If each card is one tenth of a millimeter thick, then a full stack will be almost 90 meters high!

Realization of the case n = k = 3


After I figured out the whole kitchen, it was decided to create a simple prototype demonstration of the extended version of the game for all values ​​of n and k from 1 to 3. However, when it came to programming itself, my enthusiasm subsided slightly and I decided to limit myself to the case n = k = 3 (N = 10). Since this is just a demonstration for the article, it was decided not to bother with the graphics, but to make an almost textual version of the game. So, three categories are letters (from A to J), numbers (from 0 to 9 - it’s very fortunate that we have a decimal number system) and special characters (percent, dollars, etc.) Thus, each “item” Is a set (unordered) of three characters (letter + number + special character): A0%, B1 $, etc. The game is designed for one player who is given 100 seconds to guess things. Choosing the right item adds 1 to the score, wrong - decreases the score by 1 (but only to zero). The game is implemented in HTML + JS and posted here here (tested only under chrome). The interface is very simple:



A card with three objects is shown in the upper row, and in the lower row are the objects themselves. It is necessary to select from the bottom row an object that is either on the card (all three symbols coincide), or an object that is not a single symbol on the card. In this example, the right choice is a card with the letter G. A little obfuscation (mixing “objects” and symbols in “objects”) is used to complicate the game. Note that the original version of “Lamb” is also obfuscated - objects have different sizes and are located on the card in different ways (in addition, real objects are constantly mixed by the players themselves during the game). Good luck to those who dare to play (my record so far is about 6 guessed items)!

Thank you all for your attention!

PS: And what does orthogonal polynomials have to do with it, the attentive reader will ask. Honestly, I don’t know! But if we take the formula for Q and substitute k = 2 into it, then we get a numerical sequence that starts like this: 1, 9, 120, 2100, etc. There is such a wonderful site - a dictionary of integer sequences, which allows you to find the sequence itself using several elements of the sequence (such as the game “Guess the melody”). I drove the numbers found there and the only sequence was found that is connected precisely with the coefficients of the orthogonal polynomials ... Testing showed that the formulas (mine and them) are identical. I was not too lazy, found and downloaded the original article , my numbers turned out to be the third oldest coefficients in polynomials obtained in some way in the process of the inverse Laplace transform . Unfortunately, what connection between these polynomials and “Lamb” I failed to understand ...