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.

Pegs jumping

Matt Parker’s newest Maths Puzzle asks you to provide the shortest solution to a triangular peg jumping puzzle. Start with ten pegs in ten holes arranged in a triangle:

Remove one peg. Now start jumping pegs, checkers style, but in any of six directions. For instance if peg 1 is removed then you can jump peg 4 over peg 2 into position 1, or peg 6 over peg 3 into position 1. The jumped peg is removed. That’s a move, but if you can jump two or more pegs in succession with the same peg (removing them all) that counts as a single move too. Non jumping moves are not allowed. Keep going until you’re left with only one peg, or there are no legal jumps.

There are ten pegs but really only three pegs to consider removing: A corner peg like 1, an edge peg like 2, or the center peg, 5. In each case what’s the best strategy for clearing the board? Can you clear the board, and in how few moves? For bonus points, can you find ways of winning with the last peg left in a given position?

Continue reading “Pegs jumping”

Euler plays Ingress

In the game Ingress you capture portals (by visiting real world locations), and then you can link pairs of portals together. You get points for doing that. If three portals are mutually linked with three links, forming a triangle, then they make a control field, and that’s a good thing if only because you get a lot of points for doing that. So if you’re trying to level up, one way is to find a lot of portals close together and circulate between them, capturing them and linking them.

One rule of linking, though, is that links can’t cross. If you want to link two portals, and a straight line segment between them intersects some other link, then tough luck: you can’t link them.

(Technically, if the Earth is regarded as a sphere, presumably links are great circle segments and control fields are spherical triangles. But for our purposes we pretend we’re working in a plane. Links are line segments, control fields are Euclidean plane triangles.)

So a question you might ask is, for some collection of portals, is there an optimal way to link them? Can you make more links or more control fields if you do it one way than if you do it another?

Answer: No. If you start creating links, and keep adding links until no more links are possible, then regardless of how you decide which links to make, you always get the same number of links, and the same number of control fields.

And how many is that?

You get the answer using the Euler characteristic. For any convex polyhedron,

F - E + V = 2

where F, E, and V are respectively the number of faces, edges, and vertices the polyhedron has. A cube, for instance, has 6 faces, 12 edges, and 8 vertices:

6 - 12 + 8 = 2 .

What do polyhedra have to do with portals? Well, the same idea applies to any connected planar graph (a graph with non crossing edges), which can be thought of as the shadow of a polyhedron, provided you realize every region of the plane bounded by edges is a face, including the region extending to infinity. So this graph

also has 6 faces, 12 edges, and 8 vertices, if you count as faces the central quadrilateral, the four quadrilaterals surrounding it, and the infinite region surrounding them.

Viewed as linked Ingress portals, though, it’s not maxed out; in fact, there are no control fields because none of the polygons are triangles. So you can add more links until you have, for instance

and now there are 11 faces, 17 edges, and 8 vertices; 11-17+8=2.

But to maximize links and control fields, all the polygons in the graph, except the external one, must be triangles. Each of the F-1 triangular faces has 3 edges. But E\ne 3(F-1), because where two triangles adjoin, a single edge is one of the bounding edges of both triangles. It serves as two edges, in a way. On the other hand, edges of triangles along the boundary are shared with the external polyhedron. So if we regard the external polyhedron as contributing zero edges then each internal triangle (not along the boundary) contributes 3/2 edges, and each boundary triangle contributes 2 edges. Or

E = \frac{3}{2}N + \frac{1}{2}N_b

where N=F-1 is the number of triangles and N_b is the number of boundary triangles, which is the same as the number of edges or vertices in the bounding polygon (which is the convex hull of all the vertices). Solving for N,

N = \frac{2}{3}(E-\frac{N_b}{2})

Then combining with the Euler characteristic,

\frac{2}{3}(E-\frac{N_b}{2})+1-E+V = 2

or

E=3V-N_b-3

In the above diagram, V = 8 and N_b = 4 so E = 24-4-3 = 17, which is what we see. This tells us no matter how we link portals, once we’ve made all possible links, the number of links we end up with is the same. And the number of control fields, N, is

N = \frac{2}{3}(3V-N_b-3-\frac{N_b}{2}) = 2V-N_b-2

And again in the above diagram, N = 2\times 8-4-2 = 10 which is correct. No matter how we link a given set of portals, we end up with a fixed number of control fields. All that matters is the number of portals, and the number in the convex hull.

Holographic Fifteen

Here’s a pretty good, simple discussion of the holographic principle. Its main failing is that it conveys the impression that the holographic principle is true! And maybe it is, but it’s only been proved for certain particular cases… not for the universe we live in.

For more on the concept of duality, think about the following game which I’ll call “Fifteen”. (I’ve forgotten where I first read about this. Anyone know of where this has been written up before?) We have nine cards bearing the numbers 1 through 9. Deal them out face up, and then you and I take turns picking up one card at a time. If at any point one of us has three cards in hand that add to 15, that person wins. (If we pick up all nine cards and neither of us has three that add to 15, it’s a draw.)

So for instance:

  1. I take 5.
  2. You take 1.
  3. I take 6.
  4. You take 4.
  5. I take 7.
  6. You take 2.
  7. I take 3 and win, because I have 5 + 7 + 3 = 15.

Is this game a win for one player or the other, and what’s the optimum strategy? Think it over before continuing.

Time’s up!

Okay… think about it like this. I said “Deal [the cards] out face up” but didn’t specify how. It doesn’t matter how, but suppose you do it like this:

8 1 6
3 5 7
4 9 2

That of course is a magic square of order 3. Each row, each column, and each diagonal sums to 15. In fact, as you can easily figure out, those are the only eight sets of three distinct integers in the range 1 to 9 that sum to 15.

So when you’re alternating picking up cards, the first to take all the cards a line of three — row, column, or diagonal — wins. Sound familiar? Right: Tic-Tac-Toe (or Naughts and Crosses, or, as someone once told me they call it in Norway, Swedish Chess). Fifteen and Tic-Tac-Toe are not the same game, but there’s a duality between them: The rules of either one map onto the rules of the other, and given a situation in one game, there’s a corresponding situation in the other. For example, the penultimate situation in the example game above (I hold 5, 6, and 7, you hold 1, 2, and 4, and it’s my turn) corresponds to the Tic-Tac-Toe position

   | O | X
-----------
   | X | X
-----------
 O |   | O

and the winning Tic-Tac-Toe move corresponds to my taking 3. So there’s a winning strategy in Fifteen for the first player, which is dual to the winning strategy in Tic-Tac-Toe.

Likewise the holographic principle asserts that a three dimensional universe is dual to its two dimensional surface (let’s not get into what “surface of the universe” actually means… good question but not for here and now); different mathematics describes the physics of the volume and the surface, but there is a mapping from either onto the other, and given a configuration of the volume, there’s a corresponding configuration of the surface, and vice versa. Knowing what happens on the surface, you can map that onto the volume to find what happens there, and vice versa.

 

2048

Lately I’ve been spending way too much time playing 2048 by Gabriel Cirulli. It’s a ridiculously simple (to play; not to win) puzzle game: you use the arrow keys to slide numbered tiles around on a 4 by 4 grid; tiles with the same number merge when they collide to form one tile with double the number; a 2 or 4 tile drops randomly on each turn. You “win” if you make a 2048 tile, but you can then go on to try to increase your score after that.

Given the random element there’s no guaranteed winning strategy. But some general principles tend to work for me:

I try to keep my highest numbers in the bottom row, with the highest one in the lower right corner. The point is that, say, a 512 can’t merge with anything but another 512; if there’s a 512 next to a 2, the 2 gets “starved” because you can’t “feed” it from that direction until you’ve built it up to 512 (or you move the 512 and 2 apart). On the other hand, it’s great to have a 256 next to a 512 because once you “feed” the 256 and turn it into a 512, you can then merge the two 512s right away.

Keeping the high numbers in the bottom row means I almost never  use the up arrow. Lift the bottom row and you’re likely to get a 2 or 4 placed under it! Where it’ll starve, taking up space; meanwhile the high number it’s shoved up is starving low numbers around it.

I also try not to use the left arrow unless the bottom row is filled, or there are no legal right arrow or down arrow moves. Again, if you move the bottom row left, you run the risk of getting a 2 or 4 shoved in on the lower right next to your biggest number. It’s not likely, unless there are few vacant spaces in the grid, but it can happen.

If the bottom row is full (and there are no pairs to merge in it) then the left arrow is safe, of course.

So most of my action happens on the lower left. I build up a number on the left side (first or second position from the left) of the second row I can merge with the number below it. Then merge. Repeat until there’s a mergeable pair in the bottom row. Arrow right to merge them… and now things are dangerous, the bottom row’s not full and I try to avoid left arrows until a tile appears in the left column and I can drop it to the bottom. Occasionally I run out of right and down moves in that situation and have to hold my breath, hit the left arrow, and hope the new tile doesn’t show up in the bottom row. If it does it’s hard to recover the game, once you’ve built up the highest number to 256 or so. If it doesn’t, of course I always move right on the next move.

Of course it’s good to have numbers in a powers-of-two sequence orthogonally connected. Then when you get two of the lowest number next to one another you can merge them, then merge that with the next, merge that with the next, and so on, eating up the whole sequence at once.

Other than that, I pretty much play by learned instinct based on previous games. Lately if I can avoid stupid moves (like an ill-conceived up, or left with the bottom row unfilled) I find I can get to 2048 a fair fraction of the time. Maybe more than half.

An easier version of the game is here: http://siva1456.github.io/2048/ (thanks, Louis Nick) (Actually it’s easier to win, but about as hard to play once you keep going.) Another version, very doge, such hard, is here: http://doge2048.com/

I’m going to brag by putting up an image of my best game. Feel free to avoid looking at it if it’ll just irritate you. Feel free not to rub my face in it if you’ve done better.

Screen Shot 2014-03-18 at 3.44.42 PM

Update: Of course my best has gotten better this past week, and the other day I astonished myself with this result:

Screen Shot 2014-03-24 at 11.03.02 AM

I’ve now retired from 2048. No really.