mscroggs.co.uk
mscroggs.co.uk

subscribe

# Blog

## Archive

Show me a random blog post
▼ show ▼
2018-04-29

## Building MENACEs for other games

Two years ago, I built a copy of MENACE (Machine Educable Noughts And Crosses Engine). Since then, it's been to many Royal Institution masterclasses, visted Manchester and met David Attenborough. When I'm not showing them off, the 304 matchboxes that make up my copy of MENACE live in this box:
This box isn't very big, which might lead you to wonder how big MENACE-style machines would be for other games.

### Hexapawn (HER)

In A matchbox game learning-machine by Martin Gardner [1], the game of Hexapawn was introduced. Hexapawn is played on a 3×3 grid, and starts with three pawns facing three pawns.
The pieces move like pawns: they may be either moved one square forwards into an empty square, or take another pawn diagonally (the pawns are not allowed to move forwards two spaces on their first move, as they can in chess). You win if one of your pawns reaches the other end of the board. You lose if none of your pieces can move.
The game was invented by Martin Gardner as a good game for his readers to build a MENACE-like machine to play against, as there are only 19 positions that can face player two, so only 19 matchboxes are needed to make HER (Hexapawn Educable Robot). (HER plays as player two, as if player two plays well they can always win.)

### Nine Men's Morris (MEME)

In Nine Men's Morris, two players first take turns to place pieces on the board, before taking turns to move pieces to adjacent spaces. If three pieces are placed in a row, a player may remove one of the opponent's pieces. It's a bit like Noughts and Crosses, but with a bit more chance of it not ending in a draw.
In Solving Nine Men's Morris by Ralph Gasser [2], the number of possible game states in Nine Men's Morris is given as approximately $$10^{10}$$. To build MEME (Machine Educable Morris Engine), you would need this many matchboxes. These boxes would form a sphere with radius 41m: that's approximately the length of two tennis courts.
MEME: Machine Educable Morris Engine
As a nice bonus, if you build MEME, you'll also smash the world record for the largest matchbox collection.

### Connect 4 (COFFIN)

In Symbolic classification of general two-player games by Stefan Edelkamp and Peter Kissmann [3], the number of possible game states in Connect 4 is given as 4,531,985,219,092. The boxes used to make COFFIN (COnnect Four Fighting INstrument) would make a sphere with radius 302m: approximately the height of the Eiffel Tower.
COFFIN: COnnect Four Fighting INstrument

### Draughts/Checkers (DOCILE)

In Solving the game of Checkers by Jonathan Schaeffer and Robert Lake [4], the number of possible game states in Draughts is given as approximately $$5\times10^{20}$$. The boxes needed to build DOCILE (Draughts Or Checkers Intelligent Learning Engine) would make a sphere with radius 151km.
DOCILE: Draughts Or Checkers Intelligent Learning Engine
If the centre of DOCILE was in London, some of the boxes would be in Sheffield.

### Chess (CLAWS)

The number of possible board positions in chess is estimated to be around $$10^{43}$$. The matchboxes needed to make up CLAWS (Chess Learning And Winning System) would fill a sphere with radius $$4\times10^{12}$$m.
CLAWS: Chess Learning And Winning System
If the Sun was at the centre of CLAWS, you might have to travel past Uranus on your search for the right box.

### Go (MEGA)

The number of possible positions in Go is estimated to be somewhere near $$10^{170}$$. To build MEGA (Machine Educable Go Appliance), you're going to need enough matchboxes to make a sphere with radius $$8\times10^{54}$$m.
MEGA: Machine Educable Go Appliance
The observable universe takes up a tiny space at the centre of this sphere. In fact you could fit around $$10^{27}$$ copies of the universe side by side along the radius of this sphere.
It's going to take you a long time to look through all those matchboxes to find the right one...

#### References

A matchbox game learning-machine by Martin Gardner. Scientific American, March 1962. [link]
Solving Nine Men's Morris by Ralph Gasser. Games of No Chance 29, 1996. [link]
Symbolic classification of general two-player games by Stefan Edelkamp and Peter Kissmann. in Advances in Artificial Intelligence (edited by A.R. Dengel, K. Berns, T.M. Breuel, F. Bomarius, T.R. Roth-Berghofer), 2008. [link]
Solving the game of Checkers by Jonathan Schaeffer and Robert Lake. Games of No Chance 29, 1996. [link]

### Similar posts

 MENACE MENACE at Manchester Science Festival The Mathematical Games of Martin Gardner Origins of World War I

Comments in green were written by me. Comments in blue were not written by me.

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "zebra" in the box below (case sensitive):
2018-03-23

## A 20,000-to-1 baby?

This morning, I heard about Arnie Ellis on the Today programme. Arnie is the first baby boy to be born in his family in five generations, following ten girls. According to John Humphrys, there is a 20,000-to-1 chance of this happening. Pretty quickly, I started wondering where this number came from.
After a quick Google, I found that this news story had appeared in many of today's papers, including the Sun and the Daily Mail. They all featured this 20,000-to-1 figure, which according to The Sun originally came from Ladbrokes.

### What is the chance of this happening?

If someone is having a child, the probability of it being a girl is 0.5. The probability of it being a boy is also 0.5. So the probaility of having ten girls followed by a boy is
$$\left(\tfrac12\right)^{10}\times\tfrac12=\frac1{2048}.$$
If all 11 children were siblings, then this would be the chance of this happening—and it's a long way off the 20,000-to-1. But in Arnie's case, the situation is different. Luckily the Daily Mail article, there is an outline of Arnie's family tree.
Here, you can see that the ten girls are spread over five generations. So the question becomes: given a baby, what is the probability that the child is male and his most recently born ten relatives on their mother's side are all female?
Four of the ten relatives are certainly female—Arnie's mother, grandmother, great grandmother and great great grandmother are all definitely female. This only leaves six more relatives, so the probability of a baby being in Arnie's position is
$$\left(\tfrac12\right)^{6}\times\tfrac12=\frac1{128}.$$
This is now an awful lot lower than the 20,000-to-1 we were told. In fact, with around 700,000 births in the UK each year, we'd expect over 5,000 babies to be born in this situation every year. Maybe Arnie's not so rare after all.
This number is based on the assumption that the baby's last ten relatives are spread across five generations. But the probability will be different if the relatives are spread over a different number of generations. Calculating the probability for a baby with any arrangement of ancestors would require knowing the likelihood of each arrangement of relatives, which would require a lot of data that probably doesn't exist. But the actual anwer is probably not too far from 127-to-1.

### Where did 20,000-to-1 come from?

This morning, I emailed Ladbrokes to see if they could shed any light on the 20,000-to-1 figure. They haven't got back to me yet. (Although they did accidentally CC me when sending the query on to someone who might know the answer, so I'm hopeful.) I'll update this post with an explanaation if I do hear back.
Until then, there is one possible explanation for the figure: we have looked at the probability that a baby will be in this situation, but we could instead have started at the top of the family tree and looked at the probability that Beryl's next ten decendents were girls followed by a boy. The probability of this happening will be lower, as there is a reasonable chance that Beryl could have no female children, or no children at all. Looking at the problem this way, there are more ways for the situation to not happen, so the probability of it happening is lower.
But working the actually probability out in this way would again require data about how many children are likely in each generation, and would be a complicated calculation. It seems unlikely that this is what Ladbrokes did. Let's hope they shed some light on it...

### Similar posts

 World Cup stickers 2018, pt. 3 World Cup stickers 2018, pt. 2 A bad Puzzle for Today World Cup stickers 2018

Comments in green were written by me. Comments in blue were not written by me.

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "tae" backwards in the box below (case sensitive):
2018-03-22

## World Cup stickers 2018

Back in 2014, I worked out the cost of filling an official Panini World Cup 2014 sticker book. Today, the 2018 sticker book was relased: compared to four years ago, there are more stickers to collect and the prices have all changed. So how much should we expect it to cost us to fill the album this time round?

### How many stickers will I need?

There are 682 stickers to collect. Imagine you have already stuck $$n$$ stickers into your album. The probability that the next sticker you buy is new is
$$\frac{682-n}{682}.$$
The probability that the second sticker you buy is the next new sticker is
$$\mathbb{P}(\text{next sticker is not new})\times\mathbb{P}(\text{sticker after next is new})$$ $$=\frac{n}{682}\times\frac{682-n}{682}.$$
Following the same method, we can see that the probability that the $$i$$th sticker you buy is the next new sticker is
$$\left(\frac{n}{682}\right)^{i-1}\times\frac{682-n}{682}.$$
Using this, we can calculate the expected number of stickers you will need to buy until you find a new one:
$$\sum_{i=1}^{\infty}i \left(\frac{682-n}{682}\right) \left(\frac{n}{682}\right)^{i-1} = \frac{682}{682-n}$$
Therefore, to get all 682 stickers, you should expect to buy
$$\sum_{n=0}^{681}\frac{682}{682-n} = 4844 \text{ stickers}.$$

### How much will this cost?

You can buy the following [source]:
• Starter pack (an album and 31 stickers) for £3.99
• Sticker packs (5 stickers) for 80p
• Sticker multipacks (30 stickers) for £4.50
First of all you'll need to buy the starter pack, as you need an album to stick everything in. This comes with 31 stickers; we should expect to buy 4813 more stickers after this.
The cheapest way to buy these stickers is to buy them in multipacks for 15p per sticker. This gives a total expected cost of filling the sticker album of £725.94. (Although if your local newsagent doesn't stock the multipacks, buying 80p packs to get these stickers will cost you £774.07.)

### What if I order the last 50 stickers?

If you'd like to spend a bit less on the sticker book, Panini lets you order the last 50 stickers to complete your album. This is very helpful as these last 50 stickers are the most expensive.
You can order missing stickers from the Panini website for 22p per sticker's sticker ordering service for the 2018 World Cup doesn't appear to be online yet; but based on other recent collections, it looks like ordered stickers will cost 16p each, with £1 postage per order.
Ordering the last 50 stickers reduces the expected number of other stickers you need to buy to
$$\sum_{n=0}^{631}\frac{682}{682-n} = 1775 \text{ stickers}.$$
This reduces the expected overall cost to £291.03. So I've just saved you £434.91.

### What if I order more stickers?

Of course, if you're willing to completely give up on your morals, you could order more than one batch of 50 stickers from Panini. This raises the question: how many should you order to minimise the expected cost.
If you order the last $$a$$ stickers, then you should expect to pay:
• £3.99 for the album and first 31 stickers
• £$$\displaystyle0.15\left(\sum_{n=1}^{681-a}\frac{682}{682-n}-31\right)$$ for other stickers you need
• £$$\displaystyle \left(0.16a+\left\lceil \frac{a}{50}\right\rceil\right)$$ to order the last $$a$$ stickers
The total expected cost of filling your album for different values of $$a$$ is shown in the graph below.
The red cross shows the point at which the album is cheapest: this is when the last 550 stickers are ordered, giving a total expected cost of £120.18. That's another £170.85 I've saved you. You're welcome.
Still, ordering nearly all stickers to minimise the cost doesn't sound like the most fun way to complete the sticker book, so you probably need to order a few less than this to maximise your fun.

Of course, you can also get the cost of filling the book down by swapping your spare stickers with friends. In 2016, I had a go at simulating filling a sticker book with swapping and came to the possibly obvious conclusion that the more friends you have to swap with, the cheaper filling the book will become.
My best advice for you, therefore, is to get out there right now and start convinding your friends to join you in collecting stickers.

### Similar posts

 World Cup stickers 2018, pt. 3 World Cup stickers 2018, pt. 2 World Cup stickers Euro 2016 stickers

Comments in green were written by me. Comments in blue were not written by me.
2018-03-24
It would slightly reduce the expected cost I think, but I need to do some calculations to make sure.

I'm not certain whether they guarantee that there are no duplicates in a pack or just it's very unlikely... Follow up post looking into this coming soon
Matthew
2018-03-23
Helpful article!! My head always go into a spine with probability, but does the fact that you would not get a double within a pack affect the overall strategy or cost? My head says this is an another advantage of buying 30 packs over the 5.
RM

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "yek" backwards in the box below (case sensitive):
2018-01-05

## Origins of World War I

In 1969, Sid Sackson published his magnum opus: A Gamut of Games, a collection of 38 games that can all be played with pen and paper or a pack of cards.
One of the best games I've tried so far from the book is James Dunnigan's Origins of World War I. The original version from the book gets you to start by drawing a large table to play on, and during play requires a fair bit of flicking backwards and forwards to check the rules. To make playing easier, I made this handy pdf that contains all the information you need to play the game.

### The rules

#### Starting

Origins of World War I is a game for five players (although it can be played with 3 or 4 people; details at the end). To play you will need a printed copy of the pdf, a pen or pencil, and a 6-sided dice.
Each player picks one of the five nations along the top of the board: Britain, France, Germany, Russia, or Austria–Hungary. Once you've picked your countries, you are ready to begin.

#### Taking a turn

The countries take turns in the order Britain, France, Germany, Russia, or Austria–Hungary: the same order the countries are written across the top and down the side of the board. A player's turn involves two things: (1) adding "political factors"; (2) carrying out a "diplomatic attack".
First the player adds political factors (PFs). On their turn, Britain adds 14 PFs, France adds 12 PFs, Germany adds 16 PFs, Russia adds 10 PFs, and Austria–Hungary adds 10 PFs. These numbers are shown under the names of the countries on the left hand side of the board. A player can add at most 5 PFs to each country per turn, although they may add as many PFs as they like to their own country. The number of PFs a player adds to each country should be written in the boxes in the players column.
For example, Britain may choose to add 5 PFs in Italy, 2 in the Far East and 12 in Britain. This would be added to the board by writing the relevant numbers in the Italy, Far East and Britain rows of the Britain column.
After adding PFs, a player may choose to carry out a diplomatic attack. If so the player chooses one of the other four players to attack, and a country in which this attack takes place. Both players must have some PFs in the country where the attack takes place. The dice is rolled. The outcome of the attack depends on how much the attacker outnumbers the defender and the value rolled: these are shown to the right of the board. The three possible outcomes are: Attacker Eliminated (AE), which causes the attacker's PFs in this country to be reduced to 0; Exchange (EX), which causes both players' PFs in this country to be reduced by the same amount so that one player is left with 0; and Defender Eliminated (DE), wich causes the defender's PFs in this country to be reduced to 0.
For example, Britain may choose to attack Germany in Africa. If Britain and Germany have 10 and 4 PFs in Africa (respectively), then Britain outnumbers Germany 2 to 1. The dice is rolled. If a 1 is rolled, the attacker (Britain) is eliminated, leaving Britain on 0 and Germany on 4. If one of 2-5 is rolled, the players exchange, leaving Britain on 6 and Germany on 0. If a 6 is rolled, the defender (Germany) is eliminated, leaving Britain on 10 and Germany on 0.
The game ends after each play has played 10 turns. The number of turns may be kept track of by crossing out a number in the Turn Counter to the right of the board after each round of 5 turns.

### Scoring

If a player has 10 or more PFs in a country, then they have Treaty Rights (TR) with that country. Each player scores point by achieving TR with other countries. TR are not symmetric: if Russia has TR with Germany, then this does not mean that Germany automatically has TR with Russia.
The number of points scored by a player for obtaining TR with other countries are printed in the boxes on the board. The numbers in brackets are only scored if the TR are exclusive: ie if no other country also has TR with that country. Additionally, points are awarded to Britain, France and Germany if the objectives in the boxes at the foot of their columns are satisfied.
For example, Britain scores 3 points if they have TR with Italy, 1 point if they have TR with Greece, 2 points if they have TR with Turkey. and 4 points if they have exclusive TR with the Far East. Britain also scores 10 points if no other nation has more than 12 points.

### Alliances

During the game, players are encouraged to make deals with other players: for example, Britain may agree to not add PFs in Serbia if Russia agrees to carry diplomatic attacks against Germany in Bulgaria. Deals can of course be broken by either player later in the game.
Two players may also enter into a more formal alliance, leading to their two nations working together for the rest of the game. These alliances may not be broken. If two players are allied, then at the end of the game, their scores are added: if this total is higher than the scores of the other three players combined, then the allies win; if not, then the highest score among the other three wins.
During a game, it is possible for two different alliances to form (these must be between two different pairs of nations: a country cannot form two alliances, and three countries cannot form a three-way alliance). In this case, a pair of allies wins if their combined score is larger than the combined score of the other three players. If neither pair of allies scores this high, the unallied player wins.

### Playing with 3 or 4 players

Alliances can be used to play Origins of World War I with fewer than 5 players. To play with four players, an alliance can be formed at the start of the game, with one player playing both nations in the alliance. To play with three players, the game can be started with two alliances already in place.

If you've ready this far, then you're now fully prepared to play Origins of World War I, so print the pdf, invite 4 friends over, and have a game...

### Similar posts

 Building MENACEs for other games MENACE at Manchester Science Festival The Mathematical Games of Martin Gardner MENACE

Comments in green were written by me. Comments in blue were not written by me.

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li>
To prove you are not a spam bot, please type "bear" in the box below (case sensitive):
2018-01-02

## Christmas (2017) is over

It's 2018, and the advent calendar has disappeared, so it's time to reveal the answers and annouce the winners. But first, some good news: with your help, Santa was able to work out which present each child wanted, and get their presents to them just in time:
Now that the competition is over, the questions and all the answers can be found here. Before announcing the winners, I'm going to go through some of my favourite puzzles from the calendar.

### 4 December

Pick a three digit number whose digits are all different.
Sort the digits into ascending and descending order to form two new numbers. Find the difference between these numbers.
Repeat this process until the number stops changing. The final result is today's number.
This puzzle revealed the surprising fact that repeatedly sorting the digits of a three digit number into ascending and descending order then finding the difference will always give the same answer (as long as the digits of the starting number are all different). This process is known as the Kaprekar mapping.
If four digit starting numbers are chosen, then all starting numbers that do not have three equal digits will eventually lead to 6174. It's not as simple for five digit numbers, but I'll leave you to investigate this...

### 11 December

Two more than today's number is the reverse of two times today's number.
Ruben pointed something interesting out to me about this question: if you remove the constraint that the answer must be a three digit number, then you see that the numbers 47, 497, 4997, 49997, and in fact any number of the form 49...97 will have this property.

### 20 December

What is the largest number that cannot be written in the form $$10a+27b$$, where $$a$$ and $$b$$ are nonnegative integers (ie $$a$$ and $$b$$ can be 0, 1, 2, 3, ...)?
If you didn't manage to solve this one, I recommend trying replacing the 10 and 27 with smaller numbers (eg 3 and 4) and solving the easier puzzle you get first, then trying to generalise the problem. You can find my write up of this solution here.
Pedro Freitas (@pj_freitas) sent me a different way to approach this problem (related to solving the same question with different numbers on this year's Christmas card). To see his method, click "Show Answer & Extension" in the puzzle box above.

### 24 December

Today's number is the smallest number with exactly 28 factors (including 1 and the number itself as factors).
I really like the method I used to solve this one. To see it, click "Show Answer" above.
Solving all 24 puzzles lead to the following final logic puzzle:

2016's Advent calendar ended with a logic puzzle: It's nearly Christmas and something terrible has happened: Santa and his two elves have been cursed! The curse has led Santa to forget which present three children—Alex, Ben and Carol—want and where they live.
The elves can still remember everything about Alex, Ben and Carol, but the curse is causing them to lie. One of the elves will lie on even numbered days and tell the truth on odd numbered days; the other elf will lie on odd numbered days and tell the truth on even numbered days. As is common in elf culture, each elf wears the same coloured clothes every day.
Each child lives in a different place and wants a different present. (But a present may be equal to a home.) The homes and presents are each represented by a number from 1 to 9.
Here are the clues:
21
White shirt says: "Yesterday's elf lied: Carol wants 4, 9 or 6."
10
Orange hat says: "249 is my favourite number."
5
Red shoes says: "Alex lives at 1, 9 or 6."
16
Blue shoes says: "I'm the same elf as yesterday. Ben wants 5, 7 or 0."
23
Red shoes says: "Carol wants a factor of 120. I am yesterday's elf."
4
Blue shoes says: "495 is my favourite number."
15
Blue shoes says: "Carol lives at 9, 6 or 8."
22
Purple trousers says: "Carol wants a factor of 294."
11
White shirt says: "497 is my favourite number."
6
Pink shirt says: "Ben does not live at the last digit of 106."
9
Blue shoes says: "Ben lives at 5, 1 or 2."
20
Orange hat says: "Carol wants the first digit of 233."
1
Red shoes says: "Alex wants 1, 2 or 3."
24
Green hat says: "The product of the six final presents and homes is 960."
17
Grey trousers says: "Alex wants the first digit of 194."
14
Pink shirt says: "One child lives at the first digit of 819."
3
White shirt says: "Alex lives at 2, 1 or 6."
18
Green hat says: "Ben wants 1, 5 or 4."
7
Green hat says: "Ben lives at 3, 4 or 3."
12
Grey trousers says: "Alex lives at 3, 1 or 5."
19
Purple trousers says: "Carol lives at 2, 6 or 8."
8
Red shoes says: "The digits of 529 are the toys the children want."
13
Green hat says: "One child lives at the first digit of 755."
2
Red shoes says: "Alex wants 1, 4 or 2."

Together the clues reveal what each elf was wearing:
Drawn by Alison Clarke
and allow you to work out where each child lives and what they wanted. Thanks Adam and Alison for drawing the elves for me.
I had a lot of fun finding place names with numbers in them to use as answers in the final puzzle. For the presents, I used the items from The 12 Days of Christmas:
 # Location Present 1 Maidstone, Kent a partridge 2 Burcot, Worcestershire turtle doves 3 Three Holes, Norfolk French hens 4 Balfour, Orkney calling birds 5 Fivehead, Somerset gold rings 6 Sixpenny Handley, Dorset geese 7 Sevenhampton, Glos swans 8 Leighton Buzzard, Beds maids 9 Nine Elms, Wiltshire ladies
I also snuck a small Easter egg into the calendar: the doors were arranged in a knight's tour, as shown below.
And finally (and maybe most importantly), on to the winners: 84 people submitted answers to the final logic puzzle. Their (very) approximate locations are shown on this map:
From the correct answers, the following 10 winners were selected:
 1 M Oostrom 2 Rosie Paterson 3 Jonathan Winfield 4 Lewis Dyer 5 Merrilyn 6 Sam Hartburn 7 Hannah Charman 8 David 9 Thomas Smith 10 Jessica Marsh
Congratulations! Your prizes will be on their way shortly. Additionally, well done to Alan Buck, Alessandra Zhang, Alex Burlton, Alex Hartz, Alex Lam, Alexander, Alexander Bolton, Alexandra Seceleanu, Arturo, Brennan Dolson, Carmen Günther, Connie, Dan Whitman, David Fox, David Kendel, Edison Yifeng He, Elijah Kuhn, Eva, Evan Louis Robinson, Felix Breton, Fred Verheul, Henry Hung, Joakim Cronvall, Joe Gage, Jon Palin, Kai Lam, Keith Sutherland, Kelsey, Kenson Li, Koo Zhengqun, Kristen Koenigs, Lance Nathan, Louis de Mendonca, Mark Stambaugh, Martin Harris, Martine Vijn Nome, Matt Hutton, Matthew Schulz, Max Nilsson, Michael DeLyser, Michael Smith, Michael Ye, Mihai Zsisku, Mike Walters, Mikko, Naomi Bowler, Pattanun Wattana, Pietro Alessandro Murru, Raj, Rick, Roni, Ross Milne, Ruben, Ryan Howerter, Samantha Duong, Sarah Brook, Shivanshi, Steve Paget, Steven Peplow, Steven Spence, Tony Mann, Valentin Vălciu, Virgile Andreani, and Yasha Asley, who all also submitted the correct answer but were too unlucky to win prizes this time.
See you all next December, when the advent calendar will return.

### Similar posts

 Christmas card 2017 Christmas (2017) is coming! Christmas (2016) is over Christmas card 2016

Comments in green were written by me. Comments in blue were not written by me.
2018-01-02
Thanks! The advent calendar was great fun to take part in - and winning something in the process is the cherry on top. The riddles themselves were interesting and varied, they fitted well together in the overall puzzle, and I learned some interesting new bits of maths in the process. And now, to try my hand at the other advent calendars...

I particularly liked the riddle on the 5th of December (with walking 13 units) - it was quite tricky at first, but then I solved it by seeing that you can't end up on a square an even distance away from the centre, so the possible areas are in "circles" from the center with odd side lengths . It was quite reminiscent of showing you can't cover a chessboard with dominoes when two opposite corners are removed .
Lewis