Alex, Bert and Carl are traveling, each with their own luggage. They have just collected their luggage after arriving from their flight. They need to get themselves and their luggage to the hotel. When they go to the car rental company, the company tells them that the only car available is a tiny compact car.

The car can hold either two people or one person plus one set of luggage. Obviuosly multiple back-and-forth trips are needed to get everyone and everything to the hotel.

The airport and hotel are trustworthy places but the three men do not trust each other. Each man will ransack the luggage of another person if left alone with the luggage. Specifically Alex will ransack Bert's luggage, Bert will ransack Carl's luggage, and Carl will ransack Alex's luggage. Ransacking can occur at the airport, the hotel, or in the car. The inverse relations will not result in a ransack (Alex won't ransack Carl's luggage, etc.)

Is it possible for Alex, Bert, and Carl to get themselves and all their luggage to the hotel without anybody having an opportunity to ransack any of the luggage? If so then how?

We can evaluate the formula for the ransack situations at all places in a truth-table.

((~B & ~C & A & b) v (B & C & ~A & ~b))  v
((~C & ~A & B & c) v (C & A & ~B & ~c))  v
((~A & ~B & C & a) v (A & B & ~C & ~a))
    
We eliminate the lines (24 out of 64) showing the value "1" in the main column (under the main connective, which is the second last "v" for "OR"), because this means "danger" or "ransack situation". This gives us the 40 situations (see below) with the admissible distribution of our 6 "objects", being the assignment of the truth-values under the variables A,B,C,a,b,c: "1" = "is there"; "0" = "is not there".

Each line of the upper section has its negative image in the lower section (separated by a blank line). We can even write it side by side (as shown). Putting together pairs of positive-negative value sequences represents the situations at the airport and at the hotel.

Now we could do ourselves the steps for a "transport program". This would be like playing the abstract executable program, "guessing" a successful path in a search tree.

At the start, everyone and everything is at the airport: 111111 | 000000.
At the end, everyone and everything is at the hotel: 000000 | 111111.
To find an admissible sequence of transports between those two situations is making choices in the search tree. Here we have to consider the given condition that the car does not hold more than two people or one person plus one set of luggage.
Each reversal of the values "1" or "0" between two situations signifies the transport of someone or something. The first step cannot be a reversal of the values "1" under a,b,c alone or in a combination of it, because this would mean that the luggage drives without a person. We find the very first reasonable step in line 10:
110110 | 001001
meaning: C drives with his luggage c to the hotel.
Then, C drives back alone (step 2). Now we are in line 2.

The continuation of this "program play" is not perfect and not safe (in contrary to the elaborate and impressive program solution made by Charlie).




  Airport        |  Hotel                   Car transport
                    |
  A B C a b c  |  A B C a b c                 
  -------------+---------------------------------------------------------------------
  1 1 1 1 1 1  |  0 0 0 0 0 0         START situation
  1 1 1 1 1 0  |  0 0 0 0 0 1         Step 2
  1 1 1 1 0 1  |  0 0 0 0 1 0
  1 1 1 1 0 0  |  0 0 0 0 1 1
  1 1 1 0 1 1  |  0 0 0 1 0 0 
  1 1 1 0 1 0  |  0 0 0 1 0 1    
  1 1 1 0 0 1  |  0 0 0 1 1 0      
  1 1 1 0 0 0  |  0 0 0 1 1 1      
  1 1 0 1 1 1  |  0 0 1 0 0 0      
  1 1 0 1 1 0  |  0 0 1 0 0 1        Step 1    
  1 1 0 1 0 1  |  0 0 1 0 1 0    
  1 1 0 1 0 0  |  0 0 1 0 1 1          
  1 0 1 1 1 1  |  0 1 0 0 0 0        
  1 0 1 1 0 1  |  0 1 0 0 1 0    
  1 0 1 0 1 1  |  0 1 0 1 0 0         
  1 0 1 0 0 1  |  0 1 0 1 1 0       
  1 0 0 1 0 1  |  0 1 1 0 1 0     
  1 0 0 1 0 0  |  0 1 1 0 1 1         
  1 0 0 0 0 1  |  0 1 1 1 1 0      
  1 0 0 0 0 0  |  0 1 1 1 1 1
      
  0 1 1 1 1 1  |  1 0 0 0 0 0     
  0 1 1 1 1 0  |  1 0 0 0 0 1           
  0 1 1 0 1 1  |  1 0 0 1 0 0      
  0 1 1 0 1 0  |  1 0 0 1 0 1            
  0 1 0 1 1 0  |  1 0 1 0 0 1         
  0 1 0 1 0 0  |  1 0 1 0 1 1         
  0 1 0 0 1 0  |  1 0 1 1 0 1        
  0 1 0 0 0 0  |  1 0 1 1 1 1       
  0 0 1 0 1 1  |  1 1 0 1 0 0     
  0 0 1 0 1 0  |  1 1 0 1 0 1     
  0 0 1 0 0 1  |  1 1 0 1 1 0    
  0 0 1 0 0 0  |  1 1 0 1 1 1      
  0 0 0 1 1 1  |  1 1 1 0 0 0     
  0 0 0 1 1 0  |  1 1 1 0 0 1   
  0 0 0 1 0 1  |  1 1 1 0 1 0    
  0 0 0 1 0 0  |  1 1 1 0 1 1       
  0 0 0 0 1 1  |  1 1 1 1 0 0      
  0 0 0 0 1 0  |  1 1 1 1 0 1     
  0 0 0 0 0 1  |  1 1 1 1 1 0      
  0 0 0 0 0 0  |  1 1 1 1 1 1        END situation   


 

Edited on December 18, 2016, 1:14 pm

Edited on December 18, 2016, 1:18 pm

Edited on December 18, 2016, 1:20 pm

Edited on December 18, 2016, 1:21 pm

Edited on December 18, 2016, 1:29 pm

Edited on December 18, 2016, 1:36 pm

Edited on December 18, 2016, 1:37 pm

Edited on December 18, 2016, 1:44 pm

Edited on December 18, 2016, 1:47 pm

Edited on December 18, 2016, 1:48 pm

Edited on December 18, 2016, 1:50 pm

Edited on December 18, 2016, 1:55 pm

Edited on December 18, 2016, 2:00 pm

Posted by ollie on 2016-12-18 13:08:53