Maths Olympiad Prep

Library / /4 of 7

Combinatorics Difficulty 4.8 AIME Prove it Japan

A dodecahedron and a vertex XX of the dodecahedron are given. An ant started from XX, walked along the edges of the dodecahedron, passing each of the vertices of the dodecahedron except XX just once, and returned to XX. How many such routes exist? We consider a route and its reversal to be different.

Solution

Take an arbitrary route. For each face, count the number of the edges on the face which are on the route. Since they can be neither less than 33 nor more than 44, and they add up to 2×20=402 \times 20 = 40, there exists exactly 44 faces with 44 of their edge on the route.

Now, assume that the ant passed consecutive four edges of a face as below.

---
Figure 1

Since the ant did not pass edge ABAB, the ant passed the edges BCBC and AKAK. Also, since all the vertices must be passed just once, looking at vertices EE, GG and II, it follows that the route contains edges DEDE, EFEF, FGFG, GHGH, HIHI and IJIJ. By the same reason, looking at vertices OO and PP, it follows that it contains NONO, OPOP and PQPQ. There are two ways to complete the route: one is to take the edges KLKL, LMLM, MNMN, CDCD and JQJQ; the other is to take CLCL, LMLM, MQMQ, KJKJ and DNDN.

Now we can compute how many ways are there to make a route. There are 1212 ways to choose the first face, 55 ways to choose the lacked edge, 22 ways to complete the route, and 22 ways to decide the direction. Since each route appears exactly 44 times (note that there are 44 faces of which 44 edges are contained in a route), there are 12×5×2×2÷4=6012 \times 5 \times 2 \times 2 \div 4 = 60 routes.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.