Enigma 1750

Spoiler for New Scientist Enigma 1750: “Navigating the grid” (Follow the link to see the puzzle.)

The digits 1 through 9 sum to 45, so all the numbers in the list are divisible by 9, 3, and of course 1. If the final digit were even then each number in the list would be divisible by 2, but then it would also be divisible by 6, and therefore would have five factors in the 1 to 9 range. Since some of the numbers have only four such factors, the final digit must be odd, and the five factors of the five-factor numbers must be 1, 3, 5, 7, and 9. Those numbers must end with a 5; therefore so do the four-factor numbers, whose factors then must be 1, 3, 5, and 9.

How many such numbers are there? We can start from 5 and traverse the paths backwards. From 5 (in the center square) we can go to a corner square or to an edge square. First consider corner squares; there are four options, equivalent under rotational symmetry. For each there are two possibilities for the next square, namely the two adjacent edge squares, which are equivalent under reflection symmetry. So let’s count the paths that start 5–1–2 and multiply that by 8. From 2 we could go to 6 but then could not complete a path to all 9 squares. Or we go to 3, then 6, then (similarly) 9, then 8. From there we can go to 7 and then 4, or to 4 and then 7. Or from 2 we go to 4, then 7–8–9–6–3 is forced. So there are three paths starting with 5–1–2, or 24 starting with a corner.

If from 5 we go to an edge square there again are eight symmetry equivalent ways to do the first two moves, and from there it’s forced; e.g. 5–2–3–6–9–8–7–4–1. So there are just eight paths starting with a step to an edge square.

The total number of paths then is 32, eight of each of the types shown here:

Four path types

The list of numbers is:

236987415
741236895
748963215
896321475
963214875
968741235
123698475
123698745
124789635
142369875
147896235
147896325
214789635
321478695
321478965
326987415
362147895
369874125
369874215
412369875
478963215
632147895
698741235
741236985
784123695
789632145
789632415
874123695
963214785
986321475
987412365
987412635

of which the first six are divisible by 1, 3, 5, 7, and 9, and the rest by 1, 3, 5, and 9.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s