Snakes and Ladders


Snakes and Ladders board, dated 1966, from the Auckland Museum (credit)

Snakes and Ladders is an ancient board game originating in India. It is totally random, and hence not very interesting. If players start on square #1, then after one turn, they have equal probabilities of being on squares #2, #3, #4, #5, #6, and #7. This image shows the probability distribution:

After two turns, the probability distribution is as follows (the most likely total of two dice rolls is 7, taking a player to square #8 and up a ladder to #26:

After 8 turns, players would be scattered all over the board. There is a 1% chance that any given player has won:

After 19 turns, there is a 24.7% chance that any given player has won:

This probability grows to 50.4% after 35 turns. But no matter how long you play, it remains possible (though increasingly unlikely) that nobody has won yet. Yet another reason why children tend to rapidly tire of the game.

For an alternative view of the probability analysis, see this animation:


Advertisements

American Solar Challenge Construction Progress

As I watch the lead-up to the American Solar Challenge next July, the chart above (click to zoom) shows the teams currently registered, with my estimate of current construction progress (based on a combination of social media reports and official paperwork). Team colours in the chart are my best guess in some cases. The University of Minnesota (Team 35) is in the lead (with an existing car and with most of the race paperwork done). Among teams building new cars, Italian team Onda Solare (559) and Canadian team Poly Montreal (55) lead the pack.

My ASC race information page will be updated from time to time with information on the progress of these and all the other teams. It also decodes the team numbers.


Render of Esteban9, the solar car being built by Polytechnique Montréal (picture credit)


The Game of Mu Torere

The New Zealand game of mū tōrere is illustrated above with a beautiful handmade wooden board. The game seems to have been developed by the Māori people in response to the European game of draughts (checkers). Play is quite different from draughts, however. The game starts as shown above, with Black to move first. Legal moves involve moving a piece to an adjacent empty space:

  • along the periphery (kewai), or
  • from the centre (pūtahi) to the periphery, or
  • from the periphery to the centre, provided the moved piece is adjacent to an opponent’s piece.

Game play continues forever until a draw is called (by mutual consent) or a player loses by being unable to move. Neither player can force a win, in general, so a loss is always the result of a mistake. For each player there is one “big trap” and four “small traps.” This is the “big trap” (Black wins in 5 moves):

  
The board on the left is the “big trap” for White – Black can force a win by moving as shown, which leaves only one move for White.

  
Again, Black moves as shown, which leaves only one move for White.

  
Now, when Black moves as shown, White cannot move, which means that White loses.

Here is one of the four “small traps” for White. The obvious move by Black results in White losing (but avoiding this does not require looking quite so far ahead as with the “big trap”):

Here (click to zoom) is the complete network of 86 game states for mū tōrere (40 board positions which can occur in both a “Black to move” and a “White to move” form, plus 6 other “lost” board positions). Light-coloured circles indicate White to move, and dark-coloured circles Black to move, with the start position in blue at the top right. Red and pink circles are a guaranteed win for Black, while green circles are a guaranteed win for White. Arrows indicate moves, with coloured arrows being forced moves. The diagram (produced in R) does not fully indicate the symmetry of the network. Many of the cycles are clearly visible, however:


Solar cars – From the Outback to the Oregon Trail

As I watch the lead-up to the American Solar Challenge next July, above are the entries that previously raced in the World Solar Challenge in Australia last year. Left to right from the top, they are Michigan (came 2nd), Iowa State University / PrISUm (raced in the Cruiser class), Western Sydney (came 6th), Illini (participated in the Adventure class), Principia (raced, but trailered after 2390 km), and Minnesota (raced in the Cruiser class).

Several different approaches are visible here to building a car for both races. It’s easier to do so in the Cruiser class, for a start. Illini chose to build their car for the ASC and race it non-competitively in Australia. Principia built their car for both events (unveiling it at FSGP 2017). Michigan and Western Sydney built their cars specifically for the WSC, and may have to adapt the cars for the American race (last ASC, Michigan had to modify their car, and then incurred a daily 6-minute race penalty because the modifications made the car too wide).

My ASC race information page will be updated from time to time with information on the progress of these and all the other teams.


Fibonacci and his birds (solution)

In the previous post, we described Fibonacci’s “problem of the birds” (“the problem of the man who buys thirty birds of three kinds for 30 denari”). In English:

“A man buys 30 birds of three kinds (partridges, doves, and sparrows) for 30 denari. He buys a partridge for 3 denari, a dove for 2 denari, and 2 sparrows for 1 denaro, that is, 1 sparrow for ½ denaro. How many birds of each kind does he buy?”

The man must buy at least one of each kind of bird, or he wouldn’t be buying “birds of three kinds.” Also, he must buy less than 10 partridges, because 10 partridges (at 3 denari each) would use up all his money. Similarly, he must buy less than 15 doves. We can thus make up a table of possible solutions:

Of those 126 possible solutions, only one works out correctly in terms of cost, and that’s the answer. But that’s an unbelievably tedious way of getting the answer, and you’d be rather foolish to try to solve the problem that way. The obvious approach is to use algebra. Write p for the number of partridges bought, d for the number of doves, and s for the number of sparrows. Because the man buys 30 birds, we have the equation:

p + d + s = 30

And because the costs add up to 30 denari, we have:

3 p + 2 d + ½ s = 30

Doubling that second equation gets rid of the annoying fraction:

6 p + 4 d + s = 60

If you’ve done any high school algebra, no doubt you want to subtract the first equation from this, which will eliminate the variable s:

5 p + 3 d = 30

But now what? That gives a relationship between the variables p and d, but there doesn’t seem to be enough information to get specific values for those variables.

Fibonacci solves the problem a different way. His solution is based on a key insight – the man buys 30 birds for 30 denari, so that the birds cost, on average, 1 denaro each. Fibonacci then makes up “packages” of birds averaging 1 denaro each. There are only two ways of doing this. Package A has 1 partridge and 4 sparrows (5 birds for 5 denari), and package B has 1 dove and 2 sparrows (3 birds for 3 denari). The solution will be a combination of those two packages.

Now the man can take 1, 2, 3, 4, or 5 copies of package A, leaving 25, 20, 15, 10, or 5 birds to be made up of package B. But the birds making up package B must be multiple of 3, so that the only possible answer is 3 copies of package A and 5 copies of package B. This means that the man buys 3 partridges, 5 doves, and 3×4 + 5×2 = 22 sparrows. That’s 30 birds and 3×3 + 2×5 + ½×22 = 30 denari.

Now it turns out that, had we kept on going with the algebraic approach, we would have gotten the same answer. We had:

5 p + 3 d = 30

Given that the numbers of partridges and doves (p and d) had to be positive whole numbers, that meant that p had to be a multiple of 3, and d a multiple of 5. That could only be achieved with p = 3 and d = 5.

We can also return to the diagrammatic approach. The equation:

5 p + 3 d = 30

describes the diagonal red line in the diagram below. That line only crosses one of the possible solutions, namely the dot corresponding to 3 partridges and 5 doves.

In mathematics, there’s more than one way to skin a cat. Or, in this case, a bird.


Fibonacci and his birds

The mathematician Leonardo of Pisa (better known as Fibonacci) is famous for his rabbits, but I was recently reminded of his “problem of the birds” or “the problem of the man who buys thirty birds of three kinds for 30 denari.” This problem appears in his influential book, the Liber Abaci.

The “problem of the birds” is expressed in terms of Italian currency of the time – 12 denari (singular: denaro) made up a soldo, and 20 soldi made up a lira. In the original Latin, the problem reads:

“Quidam emit aves 30 pro denariis 30. In quibus fuerunt perdices, columbe, et passeres: perdices vero emit denariis 3, columba denariis 2, et passeres 2 pro denario 1, scilicet passer 1 pro denariis ½. Queritur quot aves emit de unoquoque genere.”

In English, that translates to:

“A man buys 30 birds of three kinds (partridges, doves, and sparrows) for 30 denari. He buys a partridge for 3 denari, a dove for 2 denari, and 2 sparrows for 1 denaro, that is, 1 sparrow for ½ denaro. How many birds of each kind does he buy?”

How many birds of each kind does the man buy? It may help to cut out and play with the bird tokens below (click image to zoom). In a similar vein, what if the man buys birds as follows (still purchasing birds of all three kinds, and at the same price)?

  • 4 birds for 6 denari
  • between 6 and 10 birds for twice as many denari as birds
  • 8, 11, 13–14, 16–22, 24–25, or 27 birds for the same number of denari as birds
  • 8 birds for 12 denari
  • 12 birds for 18 denari
  • 16 birds for 12 denari
  • 28 birds for 21 denari
  • 6, 8–9, or 14 birds for 11 denari
  • 7–10, 12, 15, or 18 birds for 13 denari

Solution to the main problem here.