Problem Setting: The Game of Quarto

Here is the game of quarto.

It's a 4x4 grid with a set of pieces.

Each piece has 4 properties:  {Tall or Short}, {Light or Dark}, {Unfilled top or Filled top}, {Circular or Square}.

The goal of the game is to get 4 pieces in a row or a square which all share one property in common.  You do not pick what piece you move, however.  You select a piece for your opponent to place, and then they select a piece for you to place and so on.

Here are a few questions I was curious about:

1.  How many different ways are there to tie?  (A tie occurs if all 16 pieces are placed and no one has won).
2.  If both players play optimally, can either the 1st or 2nd player force a win, or must it always end in a draw?

Question #2 has been answered using a computer search.
Details are here:  http://wouterkoolen.info/Talks/quarto.pdf
A related analysis of the symmetries in the game:  http://web.archive.org/web/20041012023358/http://ssel.vub.ac.be/Members/LucGoossens/quarto/quartotext.htm

Math Circle Meeting 1: Maximum Seatings

The Problem:  I have 9 tables which seat 4 students each.  Whenever I change students' seats I don't want anyone to sit in the same group with someone they've sat with previously.  How many times can I change the students' seats before I have to break my rule?  In general, how many times can I re-seat if there are n tables that hold k students each?

Thoughts:  Upper Bound

Imagine person 1 keeps a list of people they've sat with before.  The list starts with 35 people on it, and each time they sit, they cross 3 names off.  After 11 seatings, they will have crossed out 33 names, and so they can't sit down again without having to sit with someone they already crossed off.

In general, with (nk - 1) others, they will be able to sit \(\lfloor\dfrac{n \cdot k - 1}{k - 1}\rfloor\) times.

A different way at the upper bound is to consider all possible pairs of students who might sit together.  There are 36 students, so there are \(\dbinom{36}{2} = 630\) possible pairs.  If 4 students sit together at a table, that's the same as \(\dbinom{4}{2} = 6\) pairs of students who can't sit together again per table.  With 9 tables, we have \(6\cdot9=54\) total pairs used up with each seating.  Therefore, we can only create \(\lfloor\dfrac{630}{54}\rfloor=11\) seatings before we run out of pairs of students who haven't sat together.

In general, with n tables of k students each there are nk students total.  This gives \(\dbinom{nk}{2} = \dfrac{nk\cdot(nk+1)}{2}\) pairs, and a total of \(\dbinom{k}{2} = \dfrac{k\cdot(k+1)}{2}\) pairs used per seating.  This gives an upper bound of \(\lfloor\dfrac{n(nk+1)}{k+1}\rfloor\) seatings.

A Graph Theoretic Setting


Let |S| = nk, the total number of students.  The complete graph on |S| nodes represents all possible pairs of students who could sit together.  Define a seating as the disjoint union of n complete subgraphs on k nodes.  We are looking for the maximum number of edge disjoint seatings.

In the diagram to the left you see a \(K_4\) subgraph of \(K_12\).  This represents 4 students sitting at a table.  Adding two more disconnected \(K_4\) subgraphs will yield one seating since we will have sat all 12 students in tables of 4.




A Construction For All 1-factors

When k = 2, we are sitting students in pairs.  In the graph setting, one seating is a complete matching (also called a 1-factor.  As you can see to the right, there are 15 unique complete matchings for \(K_6\).

We came up with a simple enumeration of all the 1-factors for \(K_{2n}\).  Label your nodes 1 to 2n.  Every node must be matched once.  There are (2n-1) other nodes that node 1 can match with.  For each of these possibilities, proceed to the next highest unmached node, and match it with each of the (2n-3) unmatched nodes (2n-3 because there were 2n-1, and we just matched 2 nodes).  For each of these possibilities, proceed to the next unmached node, and match it with each of the (2n-5) unmached nodes and so on until you have exhausted the nodes.

For n = 4 (that is, \(K_8\)), this process gives \(7 \cdot 5 \cdot 3 \cdot 1 = 105\) matchings.  For n = 3 (\(K_6\)) it gives \(5 \cdot 3 \cdot 1 = 15\) matchings (as illustrated).  In general, for \(K_{2n}\), the number of matchings is \(1 \cdot 3 \cdot 5 \cdot 7 ... \cdot (2n-1)\), which Erin noticed is equal to \(\dfrac{(2n+2)!}{(n+1)!\cdot 2^{n+1}}\)

A Simple Counting Argument For Unique Seatings

Given n tables of k students each, here is a simple counting argument for the number of unique seatings (where a student's placement within a group doesn't matter, and the tables are indistinguishable).  Start with all (nk)! permutations of students.  Divide by the k! equivalent permutations of students within each of the n tables.  Divide by the n! equivalent permutations of tables.  This gives the number of unique seatings as \(\dfrac{(nk)!}{{k!}^n \cdot n!}\).

For n = 3 and k = 2, this gives \(\dfrac{6!}{{2!}^3 \cdot 3!} = 15\) seatings, as expected.  For the original problem of n = 9 and k = 4, this gives \(\dfrac{36!}{{4!}^9 \cdot 9!} = 388035036597427985390625\) or approximately \(3.88x10^{23}\).

Expert Problem Solving

I've been reading Alan Shoenfeld's article Learning to Think Mathematically: Problem Solving, Metacognition, and Sense-Making in Mathematics, where he summarizes an interesting study about novice and expert problem-solvers that I'd like to record.

Experts Don't Get Bogged Down

The study videotaped pairs of college students attempting novel problems and coded how much time they spent in different kinds of problem-solving activity. The following was typical of novice problem solvers:

"The students read the problem, quickly chose an approach to it, and pursued that approach. They kept working on it, despite clear evidence that they were not making progress, for the full twenty minutes allocated for the problem session. At the end of the twenty minutes they were asked how that approach would have helped them to solve the original problem. They couldn't say."

They did the same for pairs of math professors, and here is what they found:

From the article:

"The first thing to note is that the mathematician spent more than half of his allotted time trying to make sense of the problem. Rather than committing himself to any one particular direction, he did a significant amount of analyzing and (structured) exploring -- not spending time in unstructured exploration or moving into implementation until he was sure he was working in the right direction. Second, each of the small inverted triangles in Figure 4 represents an explicit comment on the state of his problem solution, for example "Hmm. I don't know exactly where to start here" (followed by two minutes of analyzing the problem) or "OK. All I need to be able to do is [a particular technique] and I'm done" (followed by the straightforward implementation of his problem solution) ....

... as he worked through the problem the mathematician generated enough potential wild goose chases to keep an army of problem solvers busy. But he didn't get deflected by them. By monitoring his solution with care -- pursuing interesting leads, and abandoning paths that didn't seem to bear fruit -- he managed to solve the problem, while the vast majority of students did not."

Teaching Self-Monitoring

A second study attempted to teach students this type of self-monitoring. Shoenfeld had students spend approximately 1/3rd of their class time working on novel problems in groups of 3-4. His role was to be a roving consultant, and to press the students with the following 3 questions:

1. What (exactly) are you doing? (Can you describe it precisely?)
2. Why are you doing it? (How does it fit into the solution?)
3. How does it help you? (What will you do with the outcome when you obtain it?)

Initially, students can't answer his questions, because their way of working doesn't include thinking about them. Once they learn that he won't stop asking they begin to think about them ahead of time, before he asks. By the end of the semester, he reports, this type of thinking has become habitual.

Here is one activity graph for a pair of students who had completed this course.

He concludes:

"The point here is not that the students managed to solve the problem, for to a significant degree solving non-standard problems is a matter of luck and prior knowledge. The point is that, by virtue of good self-regulation, the students gave themselves the opportunity to solve the problem." [emphasis added]

This is like speed dating for math (if you'll indulge me the analogy for 2 paragraphs). Considering more candidate-strategies earlier gives you more chances of finding the right one for you. The difference is that speed dating prescribes a (short) fixed amount of time with each candidate. Problem solving would be more like speed dating if the speed-daters were left to decide for themselves how much time to spend with each person before moving to the next.

So how do you know when to move on? It's easy if you've run out of things to talk about, or if you don't know what to do next with your current strategy. But some people (and strategies) are seductive--it may take a long time to realize they're not taking you where you want to go. Savy and experienced daters, as well as mathematicians, learn to recognize signs of an interaction that seems promising or troubling. And this kind of subtle judgement is something that only comes with reflection on experience, I think.

What Now?

Thinking about this has suggested a few things I'm curious to try.

1). Brainstorm our options first. I might precede some problems with group- or class-wide brainstorming to get a short list of approaches that make sense to try.

2). Heuristics tell you what to try and what to look for. When I was teaching heuristics as skills, I focused on what each heuristic recommends that you try to do. Shoenfeld's questions make it obvious what this leaves out. Learning a problem-solving heuristic also means learning what to look for as you try, so you'll know whether the approach is working or not. It might also involve learning what you might do next with the kind of information you're likely to get. When first teaching students each heuristic through guided examples, I should make all three parts explicit--not just the first, as I had been doing.

3). Practice talking about all three parts. When a student was stuck, my first question was always "what could you try?" If they could give a coherent answer, I would often leave them to try. Instead, I should ask students all three questions: 1). What can you try? 2). What will tell you if it's working? (If you're looking for a pattern, can you quickly write a few types of pattern you might expect from prior experience?) 3). What then? (try to describe the pattern? connect its structure to the problem-statement? falsify it with test cases? represent it algebraically or graphically?).

Until students start to get a feel for how to answer the questions, this will probably have to be on a small-group or individual basis. Once students gain experience, I might stop all problem-solving work at 5 minutes, then at 10 minutes, then at 15, and have students write concise answers to these questions (no more than 1 minute each question).

4). Practice forced switching. Knowing how to make a mental bookmark of your current approach is immensely useful. It's required for high-level task-switching, but also to simply listen to and understand someone else's ideas. Being forced out of one's comfort zone is also sometimes required to experience the benefits of a new approach. Students might work for 5 minutes down one path, summarize their progress, then work down another path from scratch. This would be good practice for #3, and also let them know what it feels like to mentally start over, which is something that happens all the time in problem solving.