22
$\begingroup$

There was an accident at the airport! A hanging art installation fell and landed on some passengers. In addition to tearing up all their tickets and mixing up their luggage, six people sustained head injuries, causing them to have amnesia. They each remember conflicting bits and pieces of where they were from and where they were going. As the airport's logician, you have gathered reports from each of them, and determined that each person is misremembering something.

Exactly one clue from each person's list is false.

Names: Mary; Jeff; Allan; Mike; Rebecca; Katie

Origins: Orlando, FL; Chicago, IL; Los Angeles, CA; Dallas, TX; Denver, CO; New York, NY

Destinations: San Francisco, CA; Charlotte, NC; Las Vegas, NV; Phoenix, AZ; Houston, TX; Miami, FL

Luggage Colors: Black; Brown; Red; Green; Blue; White

Airlines: Delta; United; American; Southwest; Frontier; JetBlue

Concourses: A; B; C; D; E; F


Mary remembers...

  1. I was just meeting my college friend Katie before heading to my gate in concourse F.
  2. Either Mike or the person flying out of concourse F flew United. Mike is not flying out of concourse F.
  3. The black bag, which wasn't mine, was going to Houston.
  4. Jeff was headed to concourse A or B.
  5. I came from Dallas.

Jeff remembers...

  1. The person from Denver does not fly out of concourse F.
  2. Either Allan or the person from Chicago is flying out of concourse B. Allan is not from Chicago.
  3. I am flying from Orlando to Miami.
  4. The person flying to Phoenix did not fly frontier.
  5. I have a green bag.

Allan remembers...

  1. The person flying from concourse F has either a black or white bag.
  2. The person with the brown suitcase is not flying out of concourse B.
  3. The person from Los Angeles has either a white or blue bag.
  4. American Airlines doesn't fly out of concourse D.
  5. I always fly with JetBlue.

Mike remembers...

  1. I had a blue bag, and I was flying United to Houston.
  2. The person heading to concourse C has a green bag.
  3. Only one passenger's origin and destination are in the same state, and that person flies Delta.
  4. Allan is not flying Southwest.
  5. Rebecca is flying out of Gate E27.

Rebecca remembers...

  1. Whoever has the green bag is flying to Vegas on either Delta or JetBlue.
  2. I am flying to Charlotte from Denver.
  3. The black bag came from neither Orlando nor LA.
  4. Whoever is flying from New York to Phoenix needs to get to gate D14 soon before Southwest closes the door!
  5. Mary is going to Vegas.

Katie remembers...

  1. Whoever is flying Delta does not have a white bag.
  2. Nobody with a black bag is flying American Airlines.
  3. I never went to college with Mary and my luggage is brown.
  4. Whoever had a blue bag is flying Southwest.
  5. My origin and destination are both in the same state.

Solving Table

enter image description here

Here it is in Excel, with conditional formatting set up to change cell color if you input X and O.

Per Marius' suggestion, here is the solving grid as a Google Doc.

Consider the following:

  1. Third person references to an unnamed person could also refer to the person making the recollection (for example, Mary saying "The person with a green suitcase" doesn't preclude Mary from having a green suitcase).

  2. AND and OR between different statements of a clue work as boolean operators when evaluating a clue as true or false. For example: If a clue "Mary is from Dallas and Mike flew United" turns out to be false, then either Mary is not from Dallas or Mike is not flying United, or both.

  3. Implied statements, such as "Either Jeff or the person from Chicago..." (which implies that Jeff is not from Chicago), are also part of a clue's true or false value. If that clue is false, Jeff may or may not be from Chicago, as long as some part of that clue is false.

  4. This is a traditional logic grid, meaning no two people come from the same origin, are flying to the same destination, have the same luggage color, fly the same airline, or fly out of the same concourse.

$\endgroup$
  • 2
    $\begingroup$ I really appreciate the grid and the excel format, but maybe it would be a better idea to create a google doc that people can clone. I'm sure you have the best intentions, but I'm not very happy downloading files from unknown sources. $\endgroup$ – Marius Mar 17 '17 at 7:42
  • 5
    $\begingroup$ I added a Google Docs link to the solving grid. You should be able to make a copy when signed in to your Google account. $\endgroup$ – paramesis Mar 17 '17 at 13:21
  • 1
    $\begingroup$ Here is a google sheets that I made if anyone wants to help. docs.google.com/spreadsheets/d/… $\endgroup$ – user35295 Mar 20 '17 at 15:39
  • 1
    $\begingroup$ In that scenario, Mary #2 would be false. $\endgroup$ – paramesis Mar 20 '17 at 17:26
  • 2
    $\begingroup$ @SIGSEGV Attributes about airports are arbitrary, and alliterations are amusing $\endgroup$ – paramesis Mar 21 '17 at 17:21
6
+100
$\begingroup$

Here is the solution progressed further thanks to the solver referenced in another answer.

Mike

First, notice that Mary 3 and Mike 1 cannot both be true: they disagree on the bag that went to Houston.

Lets assume that Mike 1 is true. Thus, Mary 3 is false, and Mary 1,2,4,5 are all true. Notice that Mary 1 being true means Katie 3 is false since they disagree about going to college. This makes Katie 1,2,4,5 all true. But we have a contradiction because Katie 4 and Mike 1 disagree on the airline blue bag flew with.

Thus, we know that Mike 1 is false and Mike 2,3,4,5 are all true.

Mary, Jeff, and Katie

Now notice that both Katie 5 and Jeff 3 cannot both be true: one of them must be false because of Mike 3 being true.

Lets assume that Katie 5 is true, so Jeff 3 is false. Thus, Jeff 1,2,4,5 are true. Since Jeff 5 is true, and Mike 2 is true, we know Jeff flies out of concourse C. This makes Mary 4 false, so Mary 1,2,3,5 are true. Since Mary 1 is true, again, we know Katie 3 is false, which makes Katie 1,2,4,5 true.

Alternatively, lets assume Jeff 3 is true, so Katie 5 is false. Thus, Katie 1,2,3,4 are true. But Katie 3 contradicts Mary 1, so Mary 1 is false and Mary 2,3,4,5 are true. Since Mary 4 is true, and Mike 2 is true, we know Jeff 5 cannot be true. Thus, Jeff 1,2,3,4 are true.

In both cases, Mary 2,3,5 are true, Jeff 1,2,4 are true, and Katie 1,2,4 are true.

So notice here that the set Mary 1, Katie 5, and Jeff 5 is true or the set Mary 4, Katie 3, and Jeff 3 is true, but not both.

Since Mike 3 is true, we know that either Katie or Jeff fly Delta - no one else can.

So lets plug the following into the solver:

  • Mary 3, 5
  • Jeff 1, 4
  • Mike 2, 4, 5
  • Katie 1, 2, 4
  • The inference from Mike 3 that only Katie and Jeff can fly Delta

And you get this.

Jeff

Lets assume Jeff 5 is true. If Rebecca 1 and Rebecca 5 are also true, then both Mary and Jeff would be flying out of Vegas, so one of them must be false.

Either way, Rebecca 2, 3, 4 are true.

So, plug the following into the solver:

  • Jeff 5, Katie 5 (eliminate invalid origin/destination), Mary 1
  • Rebecca 2, 3, 4
  • Katie files delta due to Mike 3

And you will have this. Notice that Jeff and Katie have limited options. In fact, if Jeff doesn't fly to Vegas, then both he and her end up with trips within the same state; a violation of Mike 3. Thus we must add the fact that Jeff flies to Vegas.

Also, from Mary 2, we must infer that since Mike flies Southwest, the person out of concourse F must fly United.

Since Alan is now flying out of Chicago, Jeff 2 implies this is concourse B.

After plugging all this in, we see Since Rebecca 5 is false, Rebecca 1 must be true. But neither Delta nor JetBlue are options for the green bag as can be seen in the solver.

Therefore, we must conclude our original assumption of Jeff 5 being true is false. Therefore Jeff 3, Katie 3, and Mary 4 are true, and Jeff 5, Katie 5, and Mary 1 are false.

Lets revert back to our previous solver and add these clues:

  • Jeff 3, Katie 3, Mary 4
  • Since Jeff is the one who is taking a trip within a state, he flies with Delta due to Mike 3
  • Since Jeff is not not Allan, nor flying out of Chicago, for Jeff 2 to be true, Jeff cannot be on concourse B. This places him on concourse A.

You end up with this.

Rebecca and Alan

Looking at Rebecca 4, it is quite the load of info. If we assume it is true, then this ends up being Mike. Since he is not on concourse F, we know the United flight must be based on Mary 2. This gets us here.

Now lets look at Allan's clues. If Allan 2 is true, then it puts Katie on concourse F, making Allan 1 is false because she has a brown bag. Thus the rest of Allan's statements must be true. Allan 3 puts the white bag out of LA, and we get this.

Looking at Rebecca's clues again, if 2 is true, then by putting her out of Denver, we would have her going to Houston since they are both tied to a black suit case. This means Rebecca 2 is false and 1,3, and 5 are true. Rebecca 1 puts Mary on JetBlue going to Vegas with the green luggage. But then a second statement of Allans (Allan 5) is false.

Therefore, the original assumption of Rebecca 4 being true was false. This makes Rebecca 1, 2, 3, and 5 true.

So add Rebecca 2, 3, and 5 to the solver. Because Mary is now out of Vegas, Rebecca 1 means she has the green bag and flies JetBlue.

This makes Allan 5 false, so Allan 1,2,3,4 are all true and we get here.

Finishing Up

We now know all the false statements:

  • Mary 1
  • Jeff 5
  • Allan 5
  • Mike 1
  • Rebecca 4
  • Katie 5

The rest are true. Of these, there are a few that we haven't been able to fully realize in the truth table. There are no obvious things that can be done in the truth table. These are:

  • Mary 2
  • Jeff 2,
  • Allan 1, 3
  • Mike 3, !Mike 1

We have to make sure truth (or falsehood) of these statements is maintained.

Lets try Allan on concourse B. This puts Mike on F, which makes him fly United from Mary 2.

Now it we try Mike coming out of Chicago, then the puzzle is solved(1)! Turns out if we try Mike out of New York, solved(2)!

So now lets try Allan on F instead. From Jeff 2, we know that Chicago must be out of concourse B. Since this puts F on America, Mike must fly United from Mary 2. This yields another solution(3)

So, there are 3 solutions to this puzzle based on these clues.

1:

Mary    Dallas      Las Vegas       Green   JetBlue     C
Jeff    Orlando     Miami           Red     Delta       A
Allan   Los Angeles Phoenix         White   American    B
Mike    Chicago     Houston         Black   United      F
Rebecca Denver      Charlotte       Blue    Southwest   E
Katie   New York    San Francisco   Brown   Frontier    D

2:

Mary    Dallas      Las Vegas       Green   JetBlue     C
Jeff    Orlando     Miami           Red     Delta       A
Allan   Los Angeles Phoenix         White   American    B
Mike    New York    Houston         Black   United      F
Rebecca Denver      Charlotte       Blue    Southwest   E
Katie   Chicago     San Francisco   Brown   Frontier    D

3:

Mary    Dallas      Las Vegas       Green   JetBlue     C
Jeff    Orlando     Miami           Red     Delta       A
Allan   Los Angeles Phoenix         White   American    F
Mike    Chicago     Houston         Black   United      B
Rebecca Denver      Charlotte       Blue    Southwest   E
Katie   New York    San Francisco   Brown   Frontier    D
$\endgroup$
  • $\begingroup$ That's quite a long trial and error, but it is logically sound. You've progressed furthest so far. $\endgroup$ – paramesis Mar 23 '17 at 16:42
  • $\begingroup$ You're a few short steps from finishing your answer. I hope you do so so I can award the bounty and accept. $\endgroup$ – paramesis Mar 23 '17 at 20:52
  • $\begingroup$ @paramesis So I found 3 solutions in the end. I went through them with all the clues and they are all sound. Perhaps I am missing something? $\endgroup$ – Trenin Mar 24 '17 at 12:38
  • $\begingroup$ I looked at your grid and it looks like you're missing the implied statements, as indicated in consider the following 3 and clarified in the question comments. I mention this directly because I recognize that some logic grids do not use this convention. $\endgroup$ – paramesis Mar 24 '17 at 12:42
  • $\begingroup$ @paramesis Which implied statements am I missing? Alternatively, can you disproove any of the solutions based on the clues? I am pretty sure I went through them all and they are all satisfied. $\endgroup$ – Trenin Mar 24 '17 at 12:50
6
$\begingroup$

Finding the false statements

Denote Mary, Jeff, Allan, Mike, Rebecca, Katie by the letters M, J, A, I, R, K, so that we can denote each of the thirty given statements by a letter-number pair.

First, let's try to pinpoint which of the statements are false, thus reducing this from a liars+logic-grid puzzle to a more standard logic-grid puzzle.

  • M1 and K3 contradict each other, so at least one of these must be false.
  • I1 and K4 contradict each other, so at least one of these must be false.
  • Thus, since at least one of K3 and K4 is true, at least one of M1 and I1 must be false.
  • M3 and I1 contradict each other, so at least one of these must be false.

If I1 were true, then M1 and M3 would both have to be false; contradiction, so

I1 is false and I2, I3, I4, I5 are true.

  • R1 contradicts the combination of J3 and J5, so either R1 is false or one of J3 and J5 is.
  • Since I3 is true, J3 and K5 contradict each other, so at least one of these is false.
  • Since I2 is true, M4 and J5 contradict each other, so at least one of these is false.

If J3 and J5 are both true, then R1, K5, and M4 are all false, so K3 and M1 are both true, contradiction. So

one of J3 and J5 is false, which means J1, J2, J4 are all true.

If M1 and M4 are both true, then K3 and J5 are false, so J3 and K5 are both true, contradiction. So

one of M1 and M4 is false, which means M2, M3, M5 are all true.

If K3 and K5 are both true, then M1 and J3 are false, so M4 and J5 are both true, contradiction. So

one of K3 and K5 is false, which means K1, K2, K4 are all true.

We've also now seen that either M1, J5, K5 are true and M4, J3, K3 are false or vice versa.

  • J5 contradicts the combination of R1 and R5, so either J5 is false or one of R1 and R5 is.

Now let's get clever. If R4 is true, then A4 and J4 would be completely redundant statements. Assuming none of the information in the puzzle is unnecessary, we must have that

R4 is false and R1, R2, R3, R5 are true,

which means

M1, J5, K5 are false and M4, J3, K3 are true.

Now the only false statement we still need to find is Allan's.

Deducing the correspondences

By M5, R5, R1, I3, and I2,

Mary is flying from Dallas to Vegas with a green bag, with JetBlue, from concourse C.

Now we know which of Allan's statements is false:

A5 is false and A1, A2, A3, A4 are true.

By J3 and I3 (for origin, destination, and airline); M4 and J2 (for concourse); and M3, K3, K4, and K1 (for bag colour),

Jeff is flying from Orlando to Miami with a red bag, with Delta, from concourse A.

By M3, R2, and K3, one of Allan and Mike is flying to Houston with a black bag; by A3 and K3, the other one of Allan and Mike came from Los Angeles. So by I3, the only person who could be flying to San Francisco is Katie, which means whoever is flying from Los Angeles is flying to Phoenix.

  • ASSUME it's Mike who's flying from Los Angeles to Phoenix, and Allan who's flying to Houston with a black bag. Then we have

    Allan flying to Houston with a black bag;
    Mike flying from Los Angeles to Phoenix;
    Rebecca flying from Denver to Charlotte from concourse E;
    Katie flying to San Francisco with a brown bag.

    By J2, Allan isn't flying from Chicago, so Katie is; by elimination, Allan is flying from New York. By J2 and A2, Allan is flying from concourse B. By M2, Mike isn't flying from concourse F, so Katie is. Contradiction with A1.

So it must be Allan who's flying from Los Angeles to Phoenix, and Mike who's flying to Houston with a black bag. By K4 and M4, it must be Rebecca who's flying with a blue bag with Southwest. So

Rebecca is flying from Denver to Charlotte with a blue bag, with Southwest, from concourse E.

By A1 and A2, Katie isn't flying out of concourse B or F, so she must be D. By A4 and K2, it must be Allan who's flying with American Airlines. By M2 and J2, we can now finish off:

Mike is flying from Chicago to Houston with a black bag, with United, from concourse B.
Allan is flying from Los Angeles to Phoenix with a white bag, with American Airlines, from concourse F.
Katie is flying from New York to San Francisco with a brown bag, with Frontier, from concourse D.

$\endgroup$
  • $\begingroup$ We are doing the same thing!!! $\endgroup$ – Trenin Mar 22 '17 at 15:58
  • $\begingroup$ Assuming that none of the information is unnecessary is reasonable, but it doesn't constitute a logical proof. $\endgroup$ – paramesis Mar 22 '17 at 19:13
  • 1
    $\begingroup$ @paramesis OK, I've finally completed every single bit of logical deduction except for that one step to prove R4 is false. Will come back to include a better proof of that step, but right now I've spent WAY too long on this already, so I'm off to do other things :-) $\endgroup$ – Rand al'Thor Mar 22 '17 at 20:28
4
$\begingroup$

The answer is:

Mary, Dallas, Las Vegas, Green, JetBlue, C
Jeff, Orlando, Miami, Red, Delta, A
Allan, Los Angeles, Phoenix, White, American, F
Mike, Chicago, Houston, Black, United, B
Rebecca, Denver, Charlotte, Blue, Southwest, E
Katie, New York, San Francisco, Brown, Frontier, D

False statements:

Mary 1, Jeff 5, Allan 5, Mike 1, Rebecca 4, Katie 5

Here is the tool I used to help me solve the puzzle.

This is the completed table.

Steps in detail:

Let's find some obvious contradictions first:

1. Mary's 3rd statement contradicts with Mike's 1st.
2. Katie's 4th statement contradicts with Mike's 1st.
3. Mary's 1st statement contradicts with Katie's 3rd.

If Mike's statement 1 is true, then Mary's statement 3 and Katie's statement 4 are both false. However, number 3 above indicates that one of Mary's 1st statement and Katie's 3rd statement must be false. This means that Mike's 1st statement must be false. We fill in the table with Mike's statements 2, 3, 4, and 5.


Mike' statement 3 says that "only one passenger's origin and destination are in the same state." The possible choices here are Orlando/Miami, Los Angeles/San Francisco, and Dallas/Texas. This means that all that origins and destinations cannot fly Delta.


Let's look at some more contradictions:

1. Mary's statement 4 and Jeff's statement 5 (If Jeff has a green bag, he must be going to concourse C, according to Mike, instead of concourse A or B).
2. Katie's statement 5 and Jeff's statement 3 (According to Mike, only one person's origin and destination are in the same state).
3. Mary's 1st statement contradicts with Katie's 3rd.

We now have 2 possible sets of false statements:
1. Mary 4, Jeff 3, Katie 3.
2. Mary 1, Jeff 5, Katie 5.

Now let's assume situation 2, and fill in the table like this.


Let's go through Rebecca's statements, and see if we can find a contradiction. We find that if statements 1, 2, 3 are true, then statement 4 must be false. This would also make statement 5 true, indicating that Rebecca's 4th statement is false. The table now looks like this.

It is now obvious that Allan's statement 5 is false. We fill his true statements in like this.

Now go back to Jeff's statement 2. Since Allan is flying concourse F, the person from Chicago is flying out of concourse B. Now look at Mary's statement 2, where we see that Mike must be the one flying United.

$\endgroup$
  • 1
    $\begingroup$ I challenge your disproof of Rebecca 4. Just because it is possible for Rebecca 1, 2, 3, and 5 to be simultaneously true doesn't prove that that is the case. $\endgroup$ – paramesis Mar 22 '17 at 22:50
1
$\begingroup$

This is a partial solution, since people started to post I decided to post what I have

Logic Chart

  • 1 means there is a such possible universe
  • 0 means there cant be a possible universe

Truth Tables

  • AND = (p ∧ q) means (0,0,0);(0,1,0);(1,0,0);(1,1,1)

  • NAND = !(p ∧ q) means (0,0,1);(0,1,1);(1,0,1);(1,1,0)

  • OR = (p ∨ q) means (0,0,0);(0,1,1);(1,0,1);(1,1,1)

  • NOR = !(p ∨ q) means (0,0,1);(0,1,0);(1,0,0);(1,1,0)

Names

I'm using Mary, Jeff, Allan, Ike, Rebecca, Katie

Step 1

We know following:

  • M1(p) NAND K3(q) = 1
  • M3(r) NAND I1(s) = 1
  • I1(s) NAND K4(t) = 1
  • M1(p) OR M3(r) = 1
  • K3(q) OR K4(t) = 1

Which gives us following equation:

!(p ∧ q) ∧ !(r ∧ s) ∧ !(t ∧ s) ∧ (p ∨ r) ∧ (t ∨ q) = 1

Which has 5 solutions --> You can check here

(p,q,r,s,t) => (0,0,1,0,1);(0,1,1,0,0);(0,1,1,0,1);(1,0,0,0,1);(1,0,1,0,1)

As you can see only s = 0 is common in all 5 solutions;
which means I1 is False. Respectively, I2, I3, I4, I5 are True

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.