# Car and diamond

The latest Matt Parker’s Maths Puzzle is from James Grime and goes something like this: I have five items — a Car, a Diamond, a Goat, a pot of Bogies, and a Poke in the eye (or C, D, G, B, and P, as I will abbreviate them from here on). You can request one or more of these items, but for each item you request, I’ll instead give you two other items. Or rather, two other items will change hands, because if I’ve already given you an item I can’t give it to you again — instead you give it back to me. Each item you request results in two and only two items changing hands, and each item changes hands if either of two and only two items is requested.

So if requesting $u$ gets you $v$ and $w$, and requesting $x$ gets you $y$ and $z$, then requesting $u$ and $x$ gets you $v$, $w$, $y$, and $z$ unless two of those items are the same, in which case you’ll just get the other two, or if two are the same and the other two also are the same, you’ll get nothing.

In particular, if you request C and G, you’ll get B and P. If you request C, B, and P, you’ll get C, B, and P, but also D.

What’s the shortest request you can make that will result in you getting C and D, but nothing else?

First, it’s easy to see that if you request G, B, and P, you’ll get C and D. Requesting C and G gets you B and P, and if you then go on to request C, B, and P, you’d get C, B, P, and D, but you already have B and P so you give those back and end up with C and D. But there’s no point in requesting C twice; the second request will just undo the first request. So if you drop the requests for C and just ask for G, B, and P, you’ll get C and D.

But are there shorter requests that will work? To answer that, let’s try to work out the complete set of rules that say what items are given for each item that is requested.

We can represent such a set of rules as a matrix. Rows represent requests and columns represent bequests. Each entry is 0 or 1. Each row must have exactly two 1s and so must each column. So for instance

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 0 & 1 & 1 & 0 \\ D & 1 & 0 & 1 & 0 & 0 \\ G & 1 & 0 & 0 & 0 & 1 \\ B & 0 & 1 & 0 & 0 & 1 \\ P & 0 & 1 & 0 & 1 & 0 \end{matrix}$

would mean if you request C (first row) you get G and B; if you request D (second row) you get C and G, and so on. Notice that the main diagonal is all zeros, because you never get the item you request. And in this case if you ask for C and D, you end up with C and B, with the G from the C request canceling out the G from the D request. More generally if you ask for several items you end up with those items that appear an odd number of times in the corresponding rows.

There are, if the Python script I wrote is to be believed, 216 such matrices possible. Not something I’d want to do by hand, I’m sure I’d make mistakes. But how many of these result in BP if you request CG? That we can do by hand pretty easily. One of two things has to happen. The first is that if you request C you get B and something else, and if you request G you get P and the same something else. But that something else has to be D, because it can’t be C or G — you never get the thing you asked for. In that case we now have two rows, one column, and the main diagonal of the matrix:

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & & \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & \\ P & & 0 & & & 0 \end{matrix}$

Now consider the B and P columns. B must have a 1 in the D row and a 0 in the P row, or vice versa, and P must have a 1 in the D row and a 0 in the B row, or vice versa. So we have four possibilities:

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 1 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 0 \\ P & & 0 & & 0 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 1 \\ P & & 0 & & 0 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 0 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 0 \\ P & & 0 & & 1 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 0 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 1 \\ P & & 0 & & 1 & 0 \end{matrix}$

There’s only one way to complete the first of these matrices but two ways for each of the other three, for a total of seven:

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 0 & 0 & 1 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 0 & 0 & 1 & 0 & 1 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 0 & 1 & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 0 & 0 & 1 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 0 & 0 & 1 & 1 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 0 & 1 & 0 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 1 & 0 & 0 & 1 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 1 & 0 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 0 & 0 & 1 \\ P & 0 & 0 & 1 & 1 & 0 \end{matrix}$

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 1 & 0 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 0 & 0 & 1 & 0 & 1 \\ P & 1 & 0 & 0 & 1 & 0 \end{matrix}$

The second possibility is that if you request C you get P and D, and if you request G you get B and D. That leads to seven more matrices, which you can get from the above seven by interchanging the B and P rows and columns.

Now we can inspect these matrices to see which give you CBPD if you request CBP. Only one of the first seven does:

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 0 & 0 & 1 & 0 & 1 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}$

as does its corresponding entry in the second seven:

$\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 0 & 1 \\ D & 1 & 0 & 0 & 0 & 1 \\ G & 0 & 1 & 0 & 1 & 0 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 0 & 0 & 1 & 1 & 0 \end{matrix}$

(And Python confirms: 14 matrices give you the first result, of which 2 also give you the second.)

From the information given we can’t determine which of these two matrices is in use, but it doesn’t matter. Neither gives you CD if you request any single item, and both give you CD if you request GBP, as expected. But both also give you CD if you request… CD!

At which point insight strikes (it did me, anyway — maybe you got there quicker) and you realize there was an easier path to this solution.

We know requesting GBP gets you CD.

But that means out of G, B, and P an odd number of them (specifically 1, because the maximum would be 2) give you C. And an odd number give you D, while an even number (either 0 or 2) give you G, B, or P.

However, we know an even number of all five items — specifically 2 — give you any of the five items. So if an odd number of G, B, and P give you an item, so do an odd number of C and D, and if an even number of G, B, and P give you an item, so do an even number of C and D. This means the result of GBP must be the same as the result of CD. More generally, the result of any set of requests must be the same as the result of the complementary set of requests.

So CD must give you CD.

Is there a single item you can request that would give you CD? No. Neither C nor D will: First, because requesting an item gives you two other items; second, because if C gives you CD then that means D gives you nothing, which is false, and vice versa. Nor will G, B, or P, because if one did, then the other two would have to give you the same two items out of G, B, P. But that again would require violating the rule that requesting an item does not give you that item.

Therefore CD is the smallest request that gives you CD.

One more thing: What if we relax the rule that requesting an item doesn’t give you that item? So, for instance, requesting C could give you CG. Then the above argument still holds, except for the part about none of G, B, or P giving you CD. But that’s still true. G cannot give you CD because then there would be no way for CG to give you BP. And if one of B and P gave you CD then G (as well as the other of B and P) would have to give you two of G, B, and P. If it gave you BP then C would have to give you nothing. If it gave you GB, C would have to give you GP and then CD could not give you CD. Likewise if it gave you GP, C would have to give you GB and again CD could not give you CD. So even without that rule, CD would be the smallest request that gives you CD. Python confirms it: With the relaxed rule, there are 2040 valid matrices, of which 90 satisfy CG gives you BP, 8 also satisfy CBP gives you CDBP, and all 8 have CD as the shortest request that gives CD.