Möbius Planes, Block Designs, and the Møbee Game

The Møbee card game · Illustration from the original article

The card game Møbee was released late last year. Its rules are very simple and can be summed up in a single sentence: Turn over three cards from the deck and find the one symbol that appears on all three! The fastest player wins the round. To produce such decks—the published game includes decks at three different difficulty levels—we need some interesting combinatorial structures known as 3-designs.

Definition 1. Let $U$ be a nonempty set with $n$ elements. A $3 - (n, k, λ)$ design on $U$ is a collection of distinguished $k$ -element subsets of $U$ , called blocks, such that any three distinct elements of $U$ are contained together in exactly $λ$ blocks.

The first natural question is: for which parameters do such 3-designs exist? The following theorem gives a partial answer, in the form of three necessary conditions.

Theorem 1. (Divisibility conditions) If a $3 - (n, k, λ)$ design exists, then the following divisibility conditions hold.

$k (k - 1) (k - 2) ∣ λ n (n - 1) (n - 2)$ ,
$(k - 1) (k - 2) ∣ λ (n - 1) (n - 2)$ ,
$(k - 2) ∣ λ (n - 2)$ .

The proof is straightforward: count, respectively, the total number of blocks, the blocks containing a fixed element of $U$ , and the blocks containing a fixed pair of elements of $U$ , and use the fact that the resulting fractions must all be integers.

From now on, we assume that $λ = 1$ . Such designs are called Steiner systems.

Starting from a $3 - (n, k, 1)$ Steiner system, we can naturally construct a deck of $n$ cards in which every card carries the same number of symbols and any three cards have exactly one symbol in common. Any two cards, however, have more than one common symbol, ruling out the “trivial” deck in which a single symbol appears on every card. Let the cards correspond to the elements of $U$ , and let the symbols correspond to the blocks of the design. A symbol appears on a card precisely when its corresponding block contains the element of $U$ corresponding to that card. By definition, the resulting deck has exactly one symbol common to any three cards. Moreover, the number of cards is $n$ , the total number of distinct symbols is $\frac{n (n - 1) (n - 2)}{k (k - 1) (k - 2)}$ , and the number of symbols on each card is $\frac{(n - 1) (n - 2)}{(k - 1) (k - 2)}$ . Any two cards have exactly $\frac{n - 2}{k - 2}$ symbols in common, and each symbol appears on $k$ cards. These are the quantities obtained when proving the divisibility conditions above.

Examining the divisibility conditions for $n \geq 8$ leads to the following exercise: construct the smallest nontrivial case, where nontrivial means $k \geq 4$ .

Exercise. Construct a $3 - (8, 4, 1)$ design.

Hint. Take the vertices of a cube as the underlying set. For the blocks, use certain subsets of four vertices, including the vertex sets of the cube’s faces and of its planes of symmetry. These are all planes that contain exactly four vertices of the cube. In addition, we need the two sets of four vertices in which no two vertices are joined by an edge. By the formulas above, the number of these blocks is exactly $\frac{n (n - 1) (n - 2)}{k (k - 1) (k - 2)} = 14$ , and each vertex belongs to $\frac{(n - 1) (n - 2)}{(k - 1) (k - 2)} = 7$ blocks.

Solving this exercise allows us to construct the smallest deck in the Møbee game, consisting of eight cards.

The construction generalizes easily. Starting with the vertices of a $d$ -dimensional cube and choosing suitable four-element blocks—sets of four vertices—we obtain a design with parameters $3 - (2^{d}, 4, 1)$ . The details are left to the reader.

The following parameter triples satisfy the divisibility conditions for nontrivial designs with $n \geq 9$ and $k \geq 4$ , where the number of blocks containing a fixed element, namely $\frac{(n - 1) (n - 2)}{(k - 1) (k - 2)}$ , is at most $35$ . This is the number of symbols on each card in the resulting deck, so it is natural to impose a bound for the sake of playability:

3 - (10, 4, 1); 3 - (14, 4, 1); 3 - (16, 4, 1);

3 - (17, 5, 1); 3 - (22, 6, 1); 3 - (26, 6, 1) .

The third of these can be constructed from the vertices of a four-dimensional cube, as described above. The constructions of the first, fourth, and sixth designs lead us to the central objects of finite geometry discussed in this article: Möbius planes.

The construction of the second design in the list is not based on finite geometry and will not be discussed here. The fifth design, $3 - (22, 6, 1)$ , can be constructed by adjoining one point to the projective plane of order four, which has $4^{2} + 4 + 1 = 21$ points and the same number of lines. The new blocks, 77 in total, can be defined using certain ovals of the plane—sets of points with no three collinear, of which we need 56—and all 21 of its lines.

Möbius planes

The classical Möbius plane is an incidence structure whose points are the points on the surface of a fixed sphere in three-dimensional Euclidean space, and whose circles are the intersections of that sphere with nontangent planes. Incidence is defined in the natural way. Clearly, any three distinct points of this structure lie on exactly one circle: the intersection of the sphere with the plane determined by those three noncollinear points.

The finite analogues of the classical Möbius plane are finite Möbius planes, defined by the following three axioms.

Definition 2. A triple $(P, K, I)$ is a finite Möbius plane, where $P$ is a finite set of points, $K$ is a finite set of circles, and $I \subset P \times K$ is the incidence relation, if:

For any three pairwise distinct points $A$ , $B$ , $C \in P$ , there is exactly one circle $c \in K$ such that $(A, c) \in I$ , $(B, c) \in I$ , and $(C, c) \in I$ .
For every circle $c \in K$ and points $A$ , $B \in P$ such that $(A, c) \in I$ but $(B, c) \notin I$ , there is exactly one circle $d \in K$ incident with both $A$ and $B$ whose only point in common with the circle $c$ is $A$ .
There are four points that do not lie on a common circle.

It is easy to see that the classical Möbius plane satisfies all these requirements except finiteness.

Consider a finite Möbius plane and fix one of its points, $P$ . Remove this point from the point set, and call the circles through $P$ —with $P$ itself removed—lines. The resulting incidence structure can be shown to be a finite affine plane. The same phenomenon occurs in the classical Möbius plane when we perform stereographic projection from a chosen point on the sphere. The combinatorial properties of a finite affine plane—the number of points, the number of lines, the number of points on a line, and so on—are known. They imply corresponding combinatorial properties of the original Möbius plane, summarized in the following theorem.

Theorem 2. Let $(P, K, I)$ be a finite Möbius plane in which a circle $k \in K$ is incident with exactly $n + 1$ points. Then the following hold.

Every circle $c \in K$ is incident with exactly $n + 1$ points.
The number of points is $n^{2} + 1$ , and the number of circles is $n (n^{2} + 1)$ .
Every point is incident with $n (n + 1)$ circles.

We next show how to construct finite Möbius planes. First, we need a three-dimensional projective space coordinatized over a finite field, with points described by homogeneous coordinates. Let $F_{q}$ denote the field with $q$ elements, where $q$ is a prime power.

On the set

A = F_{q} \times F_{q} \times F_{q} \times F_{q} ⧵ {(0, 0, 0, 0)}

define a relation as follows:

ρ \subset A \times A : ((x_{1}, x_{2}, x_{3}, x_{4}), (y_{1}, y_{2}, y_{3}, y_{4})) \in ρ

$⟺$ there exists $λ \in F_{q}$ , $λ \neq 0$ , such that $λ x_{i} = y_{i}$ for every $i$ .

The relation $ρ$ can be shown to be an equivalence relation.

Let our point set $P$ consist of the equivalence classes of $A$ under $ρ$ . Introducing lines and planes on this point set gives the three-dimensional projective space denoted by $P G (3, q)$ . Its number of points is readily seen to be

| P | = \frac{q^{4} - 1}{q - 1} = q^{3} + q^{2} + q + 1 .

As an analogue of the sphere used to define the classical Möbius plane, consider a nondegenerate quadric surface in $P G (3, q)$ : an elliptic quadric. At least for odd $q$ , it is described by the equation

X_{1}^{2} + X_{2}^{2} + X_{3}^{2} + a X_{4}^{2} = 0

for a suitably chosen element $a \in F_{q}$ . For even $q$ —that is, a power of two—the equation takes a slightly more complicated form. Exactly $q^{2} + 1$ points (equivalence classes) in $P$ can be shown to satisfy it. This set of $q^{2} + 1$ points will be the point set of our Möbius plane. It is also easy to see that no three of these points are collinear. In fact, this is a point set of the largest possible size with that property in the space, known as an ovoid. Furthermore, every plane of $P G (3, q)$ either is tangent to the ovoid or intersects it in exactly $q + 1$ points. Let the circles of the Möbius plane be these latter subsets, each containing $q + 1$ points, and let incidence be containment. The structure defined in this way satisfies the axioms of a finite Möbius plane; verifying them is a relatively straightforward calculation. These finite Möbius planes, constructed over a field with $q$ elements, can indeed be regarded as $3 - (q^{2} + 1, q + 1, 1)$ designs. For $q = 3, 4, 5$ , they yield Møbee decks of 10, 17, and 26 cards, respectively, with 12, 20, and 30 symbols on each card.

Naturally, both the problem and the game can be generalized further. For example, we can introduce $4 - (n, k, 1)$ designs, from which we can construct card games in which any four cards have exactly one symbol in common, while fewer than four cards always have more than one common symbol. One such nontrivial 4-design, where nontrivial means $k \geq 5$ , is the $4 - (11, 5, 1)$ design. Its construction uses one of the Mathieu groups: the smallest one, conventionally denoted by $M_{11}$ . Each card in the resulting deck contains 30 symbols, and few people still find the game enjoyable at that level. We can go further and construct nontrivial $5 - (n, k, 1)$ designs and their corresponding card games, but the resulting decks fall outside the “playable” range. If we wish to increase the difficulty still further and construct nontrivial $6 - (n, k, 1)$ designs, with $k \geq 7$ , we unfortunately encounter the problem that none has yet been found. A result of Peter Keevash guarantees that such designs exist, although they would clearly produce decks far beyond the playable range.

Another direction is to change the value of $λ$ to two. From $3 - (n, k, 2)$ designs, we can construct decks in which any three cards have exactly two symbols in common. The players’ task is to find them as quickly as possible.

The game also has potential educational applications. For example, if we replace the symbols with paintings, literary works, or cities, we can turn over three cards and look for the painter, writer, or country represented by a work or city on each of them. Such gamification approaches may make Møbee and its variants useful in school education.

Møbee cards · Illustration from the original article

Publication of this article was supported by the National Research, Development and Innovation Office (NKFI), through OTKA grant SNN 132625.

References

[1] Hajnal, Péter: Halmazrendszerek [Set Systems]. Polygon lecture notes, 2002. In Hungarian.

[2] Kárteszi, Ferenc: Bevezetés a véges geometriákba [Introduction to Finite Geometries]. Akadémiai Kiadó, 1973. In Hungarian.

[3] Kiss, György; Szőnyi, Tamás: Véges geometriák [Finite Geometries]. Polygon, 2001. In Hungarian.

[4] Keevash, P.: The existence of designs. https://doi.org/10.48550/arXiv.1802.05900.

János Ruff
Institute of Mathematics and Informatics, Faculty of Sciences, University of Pécs

János Ruff, an assistant professor at the Institute of Mathematics and Informatics, Faculty of Sciences, University of Pécs, and his team created the MØBEE card game. It resembles the popular game Dobble, in which players look for matching symbols on cards, but is more complex and offers a different playing experience. Its website is https://mobeecards.store. A YouTube video introducing the game is available here.