Investigating Set Part 1

Random number: 93

21st November 2016

Ahh Set, you beautiful game. So innocent, so deceptive! I was introduced to you last year, and to be quite frank, I haven't really thought about you much since.

But a question occurred to me yesterday. In the classic game of Set, each card has four different properties (colour, shape, number, shading), and each property can be one of three different types. For example, I can list out every card by considering (loosely) the 'fourway cartesian product' [red,green,purple] X [squiggle,diamond,oval] X [1,2,3] X [solid,shaded,empty]. You make a Set by finding a set of three different cards such that for each of the properties, the cards that you have are either all the same , or all different. If you really don't know how set works, I'm not the guy to explain it to you. Go check the Wiki or something.

Anyhow, the whole 3/4/3 business was ugly, so let's ditch that, and form a nice little math problem on the same principles.

Suppose that \(n,m \in \mathbb{N}\), \(m \geq n\). For a given \(n\), what is the largest \(m\) that exists such that I can create an \(n\) by \(m\) matrix with the following properties:

Each entry in the matrix \(a_{ij}\) satisfies \(1 \leq a_{ij} \leq n\)
No two columns are equal
I cannot delete columns from the matrix to create a square submatrix that satisfies the 'Set' property

Where a square matrix satisfies the 'Set' property if:

For each row, either all the elements in that row are identical, or else they are all different numbers.

Reading between the lines, you'll notice that this question essentially asks the question: "If I were playing a modified game of Set where each card had \(n\) properties, each of which could be \(n\) different things, and to make a set I had to find \(n\) different cards, whats the maximum number of cards \(m\) that could be placed on a table without anybody being able to make a Set?" Well I tried writing a computer program but I buggered up halfway. Hopefully I'll come back to this problem later.