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.

Here’s a Google spreadsheet.

How odd

The new Matt Parker puzzle asks, How odd is Pascal’s triangle? Or more specifically, what percentage of the entries in the first 128 rows are odd?

Since we don’t care about the numbers themselves, just how odd they are, we can consider a modified triangle where the rule is: Each entry is the XOR (exclusive or) of the two above it. Using ones and zeroes, this triangle looks like:

Row 11
211
3101
41111
510001
6110011
71010101
811111111

An entry in this triangle is 1 if and only if the corresponding entry in Pascal’s triangle is odd. If you examine this and carry it forward, you realize this is starting to look like another famous mathematical triangle, the Sierpiński triangle. As you go to more and more rows, it gets closer to the Sierpiński triangle’s fractal nature.

In fact, what you notice is that at every row that’s a power of 2 (row 1, 2, 4, 8, 16, 32…) every entry in the row is 1. And at that point the uppermost half of the triangle is replicated twice in the lowermost half, with an “empty” triangle (all zeros) in between. For instance:

11
211
3101
41111
510001
6110011
71010101
811111111

Rows 1–2 have a triangle of size 2, composed of three 1s; rows 3-4 are two such triangles, with a “triangle” of size 1, composed of a single 0, in between. And then:

11
211
3101
41111
510001
6110011
71010101
811111111

Rows 1–4 have a triangle of size 4, composed of nine 1s and a 0; rows 3-4 are two such triangles, with a triangle of size 3, composed of six 0s, in between. And so on.

More generally, when you reach row 2^n, the first 2^{n-1} rows contain a triangle of size 2^{n-1} and the last 2^{n-1} rows contain two such triangles with an “empty” triangle of size 2^{n-1}-1 in between.

But that just means the number of 1s in the first 2^n rows is 3 times the number in the first 2^{n-1} rows. There’s one 1 in the first 1 rows, 3 in the first 2 rows, 9 in the first 4 rows, and so on: 3^n in the first 2^n rows. The total number of entries in m rows is T(m) = m(m+1)/2, and the percentage of odd entries is just the ratio of these two: P(n) = 2\times 3^n/(2^n(2^n+1)):

2^n3^nT(2^n)P(n)
233100%
491090%
8273675%
168113659.56%
3224352846.02%
64729208035.05%
1282187825626.49%

As you go to more and more rows, the percentage of odd entries gets smaller. For large n, the first 2^n rows contain a triangle of zeros filling up the middle one quarter (slightly less) of the triangle, and each of the other three quarters is a triangle containing a triangle of zeros filling up the middle one quarter, with the other three quarters being a triangle containing a triangle of zeros… well, turtles all the way down. As n approaches infinity, P(2^n) approaches equality with P(2^{n-1}). But the big triangle is a quarter empty and three quarters nonempty, so P(2^n) = 3P(2^n)/4, so in the limit, P(2^n) = 0.

Or, using the formula, \lim_{n \to \infty} P(2^n) = \lim_{n \to \infty} 2\times 3^n/(2^n(2^n+1)) = \lim_{n \to \infty} 2\times (3/4)^n = 0.

If the above triangle reminds you of a 1-dimensional cellular automaton, by the way, that’s because it is one. Specifically, you can think of it as a skewed version of Rule 60 or Rule 102 (with successive rows shifted half a cell left or right, respectively), or, if you regard adjacent numbers as actually having zeros between them, it’s Rule 90. These are the three rules in which the next state of a cell is the XOR of two of the three cells in its neighborhood.