Here’s a question that caught my eye, in a tweet from @colinthemathmo:
I had a think about this and found that it is actually a deceptively beautiful little puzzle. My answer is given below. If you want to have a go at answering it yourself, do go away and think about it, then come back when you have either resolved it, got bored or gone mad, whichever happens first.
The Question
Let’s start by setting out the question as clearly as possible (as far as I understand it).
Take a standard deck of cards, thoroughly shuffled, and deal it into thirteen piles of four, face up:
Suppose that you want the thirteen cards on the tops of the piles to all be of different denominations, such that one card of each denomination, from Ace to King, is fully visible. To achieve this, you are allowed to change the order of the cards within each pile however you wish, but you are not allowed to move cards from one pile to another.
The question is, can this always be done, or are there possible ways of dealing the cards for which it would be impossible?
Possible or Impossible?
I liked the look of this problem because the idea that you could always get that complete straight just did not feel right to me. Obviously it would work out sometimes*, but dealing a pack of cards into thirteen piles of four, surely there would be some occasions when it would not be possible to rearrange the piles to have all thirteen denominations showing?
Except…
The fact that it felt like it should not be possible, made me suspect that it probably was. These questions are often counter-intuitive – that is what makes them worth asking – so (not having a pack of cards to hand) I decided to see if I could prove that the thirteen piles could indeed always be rearranged as required.
In fact, a standard deck of cards is just part of the picture here. It is only an accident of history that we play with fifty-two cards, after all. It would also be interesting to look at the more general case. Rather than a deck of 4 suits and 13 denominations, divided into 13 piles of 4, what if we had a deck of S suits and D denominations, divided into D piles of S ? For which values of S and D can we rearrange our piles so that a card of each of the D denominations is showing?
We will start by looking at a regular deck of cards, before going on to think about the more general case at the end.
A question of perspective
The first thing to notice is that the different suits here are really a distraction. Using a standard deck of cards, all that really matters is how many copies of each denomination we have, since the problem does not differentiate between hearts, diamonds, clubs and spades. Things would be just the same if our deck of consisted of four copies of the complete suit of hearts.
More subtly, we can see that the piles and the denominations are really playing identical roles in this problem. 13 piles and 13 denominations; every card has 1 denomination and every card appears in 1 pile; every pile has 4 cards and every denomination appears 4 times. Perfect symmetry.
Bearing this symmetry in mind, we will represent a particular deal using something called a bipartite graph.
I have talked about graphs before on this site, in the article on the maths of the quiz show Pointless. Essentially they are just sets of dots (called vertices or nodes) connected by lines (called arcs or edges). A bipartite graph is simply a graph in which the vertices are divided into two sets, with edges only allowed between vertices in different sets. Vertices in the same set cannot be linked (scroll down a little and you will see a few examples of these).
For our problem, one set of vertices (which we will draw as squares) will represent the thirteen denominations (Ace to King) and the second set (drawn as circles) will represent the thirteen piles (numbered with Roman numerals, i to xiii, to avoid confusion). The edges connecting these vertices will represent the cards themselves, so we will draw an edge between K and iv if there is a King in the fourth pile.
As an example, here is a particular arrangement of the cards (the same one that was pictured above):
And here is the corresponding bipartite graph (the colours do not mean anything here, they are just to make things clearer):
You can easily check that this graph really does represent the deal shown above. There are Aces in the fifth, seventh, ninth and twelfth piles, so the square marked A is connected to the circles marked v, vii, ix and xii. Similarly, the third pile contains a Four, a Five, a Ten and a Jack, so the circle marked iii is connected to the squares marked 4, 5, 10 and J.
There are a few other things to notice about this graph.
Firstly, it is not a simple graph, by which I mean that there are some pairs of vertices that have more than one edge between them. For instance, because there are two Queens in the first pile, there are two edges connecting Q to i.
However, it is a regular graph. Since each denomination appears four times and each pile contains four cards, every vertex has precisely four edges coming out of it (we say that the vertices have degree four), which makes it a regular graph of degree four. In a few paragraphs time, this will turn out to be a very handy property.
We should be aware, though, that the graph that we have drawn might not be connected. There may be some pairs of vertices with no path between them. Happily, this is not too problematic. At worst, we might have several smaller connected regular graphs of degree four, rather than one large one. In fact, it turns out that our graph is connected, but this is not necessarily obvious just by looking at it.
And you thought it was just geographers who enjoy colouring in…
Here comes the fun part (brace yourself…). Since we have a regular graph of degree four, it must have an Eulerian cycle, a route that travels along every edge precisely once and returns to its starting point. All graphs whose vertices all have even degree have one of these.**
Even if our graph had not been connected, each of the separate components would have its own Eulerian cycle. Also, crucially, every one of these cycles must consist of an even number of edges, since any path that returns to its starting point must cross the divide between the two sets of vertices an even number of times.
It is at this point that we will deploy the mathematician’s most secret weapon: colouring in!
Because these Eulerian cycles all have an even number of edges, we can travel around each one, colouring the edges alternately red and blue, so that no two consecutive edges in a cycle have the same colour. I have done exactly this in the next picture, though you will have to take this on trust, because the one large cycle that I found is not easy to visualise:
Notice that each vertex now has two blue edges and two red edges coming out of it. This is because, when we were colouring, every time we arrived in a vertex along a blue edge, we had to leave it along a red edge (because we alternated the colours) and vice versa, so the numbers of red and blue edges meeting at each vertex must balance.
This means that if we delete all the red edges…
… we are left with a regular bipartite graph of degree two!
This time, the graph is not connected. There are actually two separate components in there, one involving the vertices A, 3, 8, J, i, vii, ix, xii, and the other involving all the others. The great thing is that, because all of our vertices still have even degree, these components each have their own Eulerian cycle and we can perform our colouring procedure all over again!
The components are just tangled loops this time, so ‘finding’ the Eulerian cycles is trivial. Here’s the first one, already coloured:
Here’s the second:
And if we delete all the red edges again, we get this:
What we have found here is called a perfect matching, a subset of the edges of the graph that matches every vertex in the set of denominations (squares) to a vertex in the set of piles (circles). More importantly, we have found a solution to the problem! The thirteen remaining edges represent thirteen cards, each in a different pile and each with a different denomination, and these thirteen cards can be shuffled to the tops of our piles to create the complete straight that we require:
You can see that the top cards here correspond to the matching that we have found. The first pile has a Jack, the second has a Six, the third has a Four and so on. This method shows us that we can indeed always arrange our thirteen piles in such a way as to have a complete straight visible on the top. Problem solved!
But that’s not all…
But hold on a minute… What if we had chosen to delete the blue edges instead of the red at the first step? Or the second? The colouring was arbitrary, there was no particular reason to delete the edges that we did.
In fact, there are four possible ways that we could have proceeded.*** We could have deleted red then red (as we did) or red then blue or blue then red or blue then blue. Each of these would have given us a different matching and a different solution to the problem. More interestingly, each of these matchings would have involved a different set of thirteen cards, one in each pile and one of each denomination.
The implication of this is the wonderful conclusion that not only can we always arrange the thirteen piles such that the top cards form a complete straight, but we can make the second cards, the third cards and the bottom cards form complete straights as well, all at the same time.
For example, here are the other three perfect matchings that we could have found:
And here if what the cards look like if we use these three matchings to create straights in the second, third and fourth cards respectively:
Considering that I started off unconvinced that it would be possible to make one complete straight, I find the discovery that you can actually make four fairly startling and really rather marvellous.
Generally speaking
So what about the general question: a deck of S suits and D denominations, divided into D piles of S ? For which values of S and D could we rearrange our piles so that a card of each of the D denominations is showing?
The answer is (I think) that this can always be done for any positive whole number values of D and S, and, once again, I am fairly sure you can get straights in all the other positions as well.
To see this, we should start by observing that the method used above does not depend on the number of denominations. We could remove all the court cards, or add in four Jokers and the method would still work just as well. Therefore, we do not need to worry about D ; the colouring method will work whatever it happens to be.
The number of suits, S, is more problematic. We can see that our method actually still works perfectly well if S is any power of two. For example, suppose that we combined two distinct decks (perhaps shuffling a charming deck of commemorative Royal Wedding cards in with a regular pack), creating a deck of 104 cards and “eight” suits (S = 8). If we dealt this deck into thirteen piles, the corresponding bipartite graph would be regular of degree eight. Our usual colouring trick would reduce it to a regular bipartite graph of degree four, but that would be the same as the problem that we have already solved. Clearly, decks with 16, 32 or 64 suits, and so on, could be dealt with in the same way.
That resolves the problem for decks with S = 2k, but what if the number of suits is not a power of two? Well, I am pretty sure that the complete straight (indeed, all S complete straights) can be created in these cases as well; in fact, I believe that I have a proof, but taking my lead from the best, I am going to omit it on the grounds that it would take up too much space. Compared to the nice colourful antics shown above, it is really quite ugly and inelegant, and given that this problem has certainly been solved before, I am sure we can all think of better things to do with our time than go through it here.****
Aftermath
In summary then, much like the question about repetitive square numbers this is another one to file under “Nice Problem, Unexpectedly Interesting Solution”. That you can create not one but four straights is a lovely result, which I still find surprising, and the fact that graph colouring holds the key (or one possible key) to explaining it is also rather pleasing.
I will now go back to keeping an eye on Twitter, waiting for the next infuriatingly distracting puzzle to pop up. Please feel free to comment/criticise/correct below.
UPDATE: Thanks to Colin Wright (whose original tweet inspired this investigation) for pointing out that the general case can be solved using Hall’s Marriage Theorem.
* Indeed, you would expect to deal out one perfect solution (where the thirteen top cards show all thirteen denominations, with no rearrangement necessary) for every 9162 attempts, more or less.
** This is quite easy to show using Hierholzer’s Algorithm. Here’s a nice video. It is also easy to show that graphs whose vertices do not all have even degree do not have Eulerian cycles, which goes right back to the famous Bridges of Königsberg.
*** That is without taking into account the fact that there were many other Eulerian cycles that we could have chosen in the original graph.
**** The principle of the proof is to show that the matching improvement algorithm (much beloved of A-level students taking Decision Maths modules) can always be applied to improve a non-perfect matching in a regular bipartite graph, by keeping track of the number of edges leading into and out of vertices on your alternating path as you build it up, thus showing that there are always “ways out” if you hit a dead-end before finding an unmatched vertex. I am sure this (or something more elegant) must be a well-known result. Either that or I have made a mistake, my answer is wrong, and I am just going to look very silly. In the (vanishingly unlikely) event of their being widespread popular demand (street protests, charity singles, questions in parliament, or similar), I will do a quick write up of my general solution and stick a link to it here. [ See also the UPDATE above.]
Digital playing card images: TES website – Playing Cards resource
Shuffling photo: CC – Essie – Wikimedia Commons
Spread deck photo: Public domain – Wikimedia Commons
Joker: Public Domain – Wikimedia Commons
Thomas Oléron Evans, 2015
Click here for the previous page in the Maths section.
Click here for the next page in the Maths section.