Who Went Hiking Alone? (hikers)

Run LPL Code  ,  PDF Document

Problem

A group of 17 persons, named A, B, …, Q went hiking. The next day, they came together with their friend James who was not on the hike. They told him that soon after the start they split into 4 groups and each group went on its own continuing hiking. Each person gave James four names with whom he was not in the same group. This information is displayed in Table 1. He was also told that one person went alone and there was a group of three persons. James then immediately told them who was the person that went alone. How did he find out?

This problem is from [1], chap.7. In the mentioned book of Alain Hertz, this problem has been interweaved in an amusing detective story, where a team of investigators using forensic science had to find out who – out of 17 suspects – was the thief, the unique person who went alone on his “walk”.

Modeling Steps

This puzzle is a nice exercise in graph theory. We name the 17 persons with the 17 first letters of the alphabet: A, B, …, Q. Each person name 4 others with whom he was not in the same group. We can represent these data in a graph: Draw a circle for each person and an edge between two persons if they were not in the same group. The graph is given in Figure 1.

---

---

The problem now is to partition the 17 circles into 4 groups in such a way that two circles in the same partition are not connected by an edge. (This problem is the same as in model coloring2.) Example: A and I are linked by an edge, hence they cannot be in the same group; on the other hand, F and J are not connected, they may be in the same group.

The problem is well known under the name of vertex coloring of a graph: Color the circles (vertices) in such a way that two connected circles must be colored with different colors. The number of colors should be as small as possible. It is well known that this problem is difficult to solve in general.

In our problem, the additional requirement is: One circle must have a unique color, and three other circles must have the same color. To formulate the problem as a mathematical model, we proceed as follows:

1. We define two sets I = {1…17} (set of persons), and K = {1…4} (set of groups (colors)).

2. The set of relations e_i,j with i,j ∈ I specifies the fact that i and j are not in the same group (list of tuples).

3. We introduces a binary variable x_i,k with i ∈ I and k ∈ K, which is 1 if person i is in group k otherwise it is 0.

4. Every person i must be in a single group k, hence

   

5. Furthermore, two persons in e_i,j cannot be in the same group, that is, for any group k and any e_i,j, i and j must be assigned to different k. Hence:

   

6. A group (say the third one) must contain exactly 3 persons:

   

7. Another group (say the fourth one) must contain exactly 1 person:

   

8. We are looking for a feasible solution.

model hikers "Who Went Hiking Alone?"; 
    set i,j:=[A B C D E F G H I J K L M N O P Q]; 
      e{i,j} := 
        [(A,*) F G H O , (B,*) A C G H , (C,*) D J K M 
         (D,*) C E P Q , (E,*) D F K O , (F,*) A E G H 
         (G,*) C E F J , (H,*) E F I K , (I,*) A G K L 
         (J,*) G I L P , (K,*) G H L Q , (L,*) J M N O 
         (M,*) A C L N , (N,*) D L O P , (O,*) E L N Q 
         (P,*) D J M N , (Q,*) D K N O]; 
    set k:=[1..4]; 
    binary variable x{i,k}; 
    constraint A{i}: sum{k} x = 1; 
    constraint B{k,e[i,j]}: x[i,k] + x[j,k] <= 1; 
    constraint C: sum{i} x[i,4]=1; 
    constraint D: sum{i} x[i,3]=3; 
    --constraint E: x['I',4]=0; 
    solve; 
    parameter 
      X{i}:=[8 2 0 8 16 14 5 11 8 4 12 8 7 8 9 6.3 9.7]; 
      Y{i}:=[11 11 7 0 7 11 9 9 7 6 6 5 4 2 4 2 2]; 
    Draw.Scale(50,50); 
    {e[i,j]} Draw.Line(X[i],Y[i],X[j],Y[j]); 
    --{i,k|x} Draw.Circle(i&'',X,Y,.3,1,0); 
    {i,k|x} Draw.Circle(i&'',X,Y,.3,k+2,0); 
  end

Solution

The four groups contain 7, 5, 3, and 1 members, they are :

Person I is the person that formed a single group, see Figure 2.

---

---

Questions

1. Give a proof – by running a model – that person I was really the person who formed a group on its own.

2. James was not only able to conclude who was the lone hiker, he also named the members of the 3-person group. How did he find out?

Answers

1. Add a constraint that person I is not in the fourth group (the group with a single person) by adding

   

   Running the model shows that the model is infeasible. Hence, person I must be in the fourth group.

2. He proceeded in the same way as in question 1. Looking at the solution: N, G, and H were together in the third group. To check if this is the unique solution he needed to check whether the three persons are really in the third group.

References