MatMod logo

Earthlings (earthling)

Run LPL Code  ,  PDF Document

Problem

August 2020. The spaceship landed. “Earth!” they shouted. They knew that earthlings are divided into three groups: those who always tell the truth, those who always lie, and those who do both, alternating between true and false statements, starting with either. “Let’s go!” said the captain. The aliens approached three earthlings, who each were from a different group, and asked, “Who won the last World Cup? Who came in second? Who came in third?” One of them responded, “Zaire first. Uruguay second. Spain third.” Another one said, “Zaire first. Spain second. Uruguay third.” The third one said, “Uruguay first. Spain second. Zaire third.” The aliens returned to their spaceship and flew back to where they came from. Do you know which response was the true ranking in the World Cup? (see [2] and [1]).

Modeling Steps

Let’s introduce a (ordered) set of 3 teams i of the Cup and an ordered set of place j they got (first, second and third). There are three type of earthlings: truth tellers, alternators and liars (set k), and one in each group (type) made a statement (set h). All four sets are ordered.

  1. We introduce a binary variable xi,j, such that xi,j = 1 if team i in the Cup got place j, hence x1,1 = if the first mentioned team in set i get the first place in the Cup.

  2. Another binary variable yh,k says which statement h was made by an earthlings of type (in group) k, hence y2,1 = 1 if the second statement was made by the truth-teller (the truth-teller is the first in the ordered set k).

  3. Two constraint are needed to assign each team to a unique place:

    ∑        ∑  xi,j = 1  forall i  xi,j = 1  forall j  j      i
  4. Two constraints are needed to link each statement to a earthling type, that is each statement was made by an earthling in a different group, and vice versa:

    ∑       ∑  yh,k = 1   forall k   yh,k = 1  forall h  h       k
  5. The three statements made could be formulated as :

    x1,1 ∧ x2,2 ∧ x3,3 , x1,1 ∧ x3,2 ∧ x2,3 , x2,1 ∧ x3,2 ∧ x1,3

    Now, one of these statement is true – let’s take the first one – if the sum of the three binaries is three: x1,1 + x2,2 + x3,3 = 3 and it is false if the sum is zero x1,1 + x2,2 + x3,3 = 0. On the other hand, the statement could be attributed to the alternator if the sum is at least 1 and at most 2.

  6. Therefore, we introduce an integer variable 0 dh 3 for each statement h. dh = 3 if statement h is true, dh = 0 if statement h is false. So, we define :

    d1 = x1,1 + x2,2 + x3,3 , d2 = x1,1 + x3,2 + x2,3 , d3 = x2,1 + x3,2 + x1,3
  7. We need to link these variables with the binaries yh,k, by defining which statement was said by the truth-teller and which by the liar: “if and only if dh = 3 then the statement h was made by the truth-teller”, so:

    dh = 3 ↔  yh,1  and   dh = 0 ↔  yh,3  forall h

Listing 1: The Complete Model implemented in LPL [4]

model earthling "Earthlings"; 
  set team,i := [Zaire, Uruguay, Spain]; 
    place ,j := ['1st', '2nd', '3rd']; 
    type  ,k := [truth_teller, alternator, liar]; 
    state ,h := [1..3] "Three statements made"; 
  binary variable 
    x{i,j}  "Team i in place j"; 
    y{h,k}  "Statement h made by type k"; 
  integer d{h} [0..3]; 
  constraint 
    TE{j}: sum{i} x = 1 "Each place j one team i"; 
    PL{i}: sum{j} x = 1 "Each team i one place j"; 
    TY{h}: sum{k} y = 1 "Each h makes one statement k"; 
    ST{k}: sum{h} y = 1 "Each statement k made by one h"; 
    --the statements made 
    S1: d[1] = x[1,1] + x[2,2] + x[3,3]; 
    S2: d[2] = x[1,1] + x[3,2] + x[2,3]; 
    S3: d[3] = x[2,1] + x[3,2] + x[1,3]; 
    T{h}: d>=3 <-> y[h,1] "The truth-teller"; 
    L{h}: d<=0 <-> y[h,3] "The liar"; 
  solve; 
  Writep(x,y,d); 
end

Solution

The solution is d3 = 3, d2 = 1, d1 = 0, hence, the earthling pronouncing the third statement is the truth-teller, the earthling with the second statement is the alternator, and the earthling saying the first statement is a liar. Note that it is needed to check the alternator: there must be any h such that 1 dh 2, otherwise no statement could be assigned to the alternator.

Without a mathematical model, one could easily tell which statement is the correct one by the following reasoning. Suppose, the first statement were the correct one, then the second could not be said by a liar because he would have said “Zaire first”, which is true. Only the earthling saying the third could then be the liar, but the earthling pronouncing the second then could not be an alternator.

So suppose the second statement is the correct one, then the earthling pronouncing the first one could not be a liar, because he would have said “Zaire first”, which is true. The earthling pronouncing the third one could not be a liar either, because he would have said “Spain second”, which is true. Hence, the earthling saying the second one must be a alternator.

Now suppose the third statement is the correct one, then the earthling pronouncing the first could be a liar, but the earthling pronouncing the second one can’t. Hence, either the first or the third is a truth-teller and the second is surely an alternator. Hence, only the third statement is the correct one, as shown by the solution of the model.

Questions

  1. Add the constraint d1 = 3 (imposing that the first statement is the correct one, and solve the model. What is the problem with this solution?

Answers

  1. There is a solution. However, the earthling with the second statement is not a true alternator. It is not enough to check 1 dh 2 to be an alternator, the three phrases must also alternate: true-false-true or false-true-false. However this is not the case for the second statement.

References

[1]   Nolan Clare. http://www.chlond.demon.co.uk/academic/puzzles.html.

[2]   Poniachik J. L. Hard-to-solve Brainteasers. Sterling, 1998.

[3]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[4]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.