0
$\begingroup$

Inspired by the card game SET, the following question came up: Laying out all 81 cards, can one find 27 Sets (in the sense of the game), all of which are Sets with four different features?

To be precise and (a bit) more general:

Consider $M = \{0,1,2\}^n$ for $n \in \mathbb{N}$.
Define a diverse Set as a three-element set $\{(x^{(i)}_1, x^{(i)}_2, \ldots, x^{(i)}_n) \in M, i = 1,2,3\} $ where no two components (“features”) are equal for two of the three elements of the set, i.e. $ x^{(i)}_1 \neq x^{(j)}_1 \wedge x^{(i)}_2 \neq x^{(j)}_2 \wedge \ldots \wedge x^{(i)}_n \neq x^{(j)}_n \quad \forall i \neq j$.

Is there a partition of $M$ in $3^{n-1}$ diverse Sets?

For $n=1$ the question is trivial, for $n=2$ the answer ist obvious and “yes”, for $n=3$ the answer is (in my view) less obvious but can still be found manually and is “yes”. What about $n=4$ (preferably without writing a program to solve it) and general $n$?

Probably the answer is known or the question can me mapped to a problem with known solution.
Any hint is appreciated.

$\endgroup$

1 Answer 1

7
$\begingroup$

Let $s\colon\{0,1,2\}\to\{0,1,2\}$ be the cyclic shift $s(x)=(x+1)\bmod 3$, and let $s_n\colon\{0,1,2\}^n\to\{0,1,2\}^n$ be defined by applying $s$ coordinate-wise. Then $s_n^3=\mathrm{id}$ and $s_n$ has no fixpoints, hence the orbits of $s_n$ partition $\{0,1,2\}^n$ into three-element sets with the required property.

$\endgroup$
2
  • 1
    $\begingroup$ Alternatively (for visualization), this is induced by the tiling of $\mathbb{Z}^n$ by diagonal lines. $\endgroup$ Sep 26, 2017 at 21:39
  • 4
    $\begingroup$ Morale: thinking of $\{0,1,2\}^2$ as $F_3^4$ and "Sets" as affine lines makes the problem trivial. $\endgroup$
    – YCor
    Sep 26, 2017 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.