Duty Of Cosmetics In China

2010 Fourth Circle letters

Statement

Several comments

solve this problem, but no details or method.

To solve such problems is well to remember a simple rule. A picture can go without passing twice for the same line only when there is none or two crosses with an odd number of lines. If there are none, then you can start at any intersection, and end up in it, and if there are two, you should start one and finish on the other.

Why is that? Because every time you come to a junction you use two lines: the input and output, so that all crosses must add an even number, except perhaps in the departure and arrival, which also is required if starting and finishing in the same place.

Knowing this, let's count how many lines arriving at each crossing. In the A match 3, B 3, C, 2, D, 4, E, 2, F 3, G 3, H 5, I, 3. That makes a total of 6 intersections (nodes, in the jargon) in odd ways. We need to remove or add at least two routes (equivalent to not go, or go twice some who are), to return four of the six peer nodes that do not suit us.

But if you want out of H, go through the roads, and back to H, we require that all nodes are peers, which will force us to go a minimum of 3 paths twice.

How can we find the combination less? Trying to study whether the shortest path travel twice or not we solve the problem (again pairs of vertices that we want to) and finding the lowest possible combination.

If you seek solutions with three paths, we find the combinations HB + FI + AG (70 + 80 + 80 = 230) and HG + IF + AB (50 + 80 + 100 = 230). Twice those roads go in any order, leads to an optimal solution. And if we try to follow more roads, more length will travel safely, since it is impossible to achieve less than 230 meters these extras.

For example, if we choose to duplicate HG, IF and AB, we can HBAHGABCDEFIDHGFIH, and will join the 1320 plus 320 extras required, ie 1550. Although there are several possible routes, as where double every time.

If we choose to duplicate HB, FI, AG, for example we go HBAHGAGFIHBCDEFIDH, obtaining new 1550 meters. Again there are several options.