Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for an elegant way to solve this rather simple logic puzzle using mathematical logic (statements, conjunctions, disjunctions, implications, tautologies, predicate logic and so on). I am not looking for a solution using combinations, variations or permutations, as I have already solved it using that method (given below).

The puzzle is:

Four men (A, B, C, D) should be seated in a boat forming a line. Can you determine the order in which they need to be seated, from the front of the boat to the back, so that all of their requests are satisfied?

Requests:

Man A: I want to be seated at one end of the boat (either first or last) only if B sits next to me.

Man B: I don't want to sit next to (either before or after) C and I don't want to be last.

Man C: I don't want to sit next to A if I am seated on one end of the boat.

Man D: I want to sit next to B or not to sit next to A, and if I am not first, then I want to be last (if not seated on the front side, he wants to sit at the back side of the boat).

There obviously are $V_{4}^{4}=P_{4} = 4! = 24$ possibilities for this exercise (not sure if the notation is universal), of which only one - "BACD", satisfies the conditions. However, had there been five elements in the example, it wouldn't have been so easy to determine the correct result by experimentation/counting values, which is why I am searching for a logical approach to the problem.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Well, D and B look like they have the most restrictive conditions so we can start with them. Say with D. Suppose D was sat at the front (he can only be first or last). Now suppose we put B second. B cannot sit next to C so C must be last, which makes A third. But then A is next to C so B is unhappy and so this arrangement doesn't work. So now we know that if D is first, B cannot be second. So C has to be second. But now wherever we put B he is unhappy.

Hence we know that D cannot be at the front, so must be at the back. We have now fixed D, so could do some experimenting to find what works (this is now suitable easy since so few combinations exist) but we can keep on purely logically:

As before, suppose B sits next to D. To keep B happy, C must be first and A second, but then C is unhappy.

So B must not sit next to D. To keep D happy, A must not sit next to D so only C can be third. (Note that at this stage we know that B and C must be arranged as we say, because anything else leads to a contradiction. It is important to distinguish this from where we start by supposing something and then have statements like "C must be first and A second" which were true only if our suppositions were correct.)

All that remains is to say that for B to be happy, he must be first. This leaves A in second place. If we know there is a solution, we do not even need to check that all the conditions hold since we have said that this is the only possible solution. (Note in some cases there may be no solutions, and we would have to check that the only possible solution is actually a solution.)

Also, this was only one way to do it, we could have started by supposing B sat at the back, or by supposing something about where one of the others were sat. It's best to start with the most restrictive condition to save yourself some time, and if you have any intuition about what would happen, make those suppositions first, and then you are more likely to stumble upon the right answer. We find the right one by excluding all others, so the closer we start to correct the quicker we get there!

Edit: With labelling as in the comments, I'll re-write the proof from the point where I said D must be at the back (say D is at 4):

D is at 4. Suppose B is at 3. $P_b \implies $ C is at 1 and hence A is at 2. But then $P_c$ is not satisfied, giving a contradiction.

So B is not at 3. Then $P_d \implies$ A is not at 3. So C is at 3. Now $P_b \implies$ B is at 1. Hence A is at 2. Now $P_a, P_b, P_c, P_d$ are all satisfied so this is the solution.

share|improve this answer
    
Good answer. I'm just interested if we could use some logic statements, or logic functions with predicates to mathematically write out all of this. Of course, we could write those requests for each man as logical functions using predicates and establish the conditions, but besides that, is there any way to elegantly and mathematically write out all that you said, and the fact that only "BACD" is the solution to the exercise? –  Alex Nov 15 '12 at 21:25
1  
@Alex We could label each condition, and re-write what I said in more rigorous language. For example, if we call the conditions for each person $P_a, P_b, ...$ and use symbols like $\implies$. I used a lot of unnecessary words since I was trying to convey the thought processes, which I now realises isn't precisely what you wanted, but it is essentially a "proof by repeated contradiction" and we could phrase it as such. Other than a more formal re-wording, or explicitly writing out the logical consequences of each condition as you suggest, I don't know of any other way to do this. –  Tom Oldfield Nov 15 '12 at 21:31
    
It would be most helpful if you could edit your post to contain that additional labeling of conditions and establishing those relationships as much as that could be done. If you could do that, than that would be the perfect solution to this question. –  Alex Nov 15 '12 at 21:34
1  
@Alex The thing is, writing out the explicit logical equivalences of the conditions would require the introduction of a lot of notation (i.e. the set of events that A is first, or the set of events that B is next to D) and would just confuse things. I feel that the only edits that would give a truly better answer would be those that replaces sentences like "to keep A happy" with "To satisfy $P_a$". Any more than that and you have to decide at what point formalism isn't making a proof more rigorous, just more cumbersome. And once the method is understood, this is something that comes naturally. –  Tom Oldfield Nov 15 '12 at 21:43
    
Alright, that makes sense. Thanks. –  Alex Nov 15 '12 at 21:46

The following seems a useful and consistent way to formalize this problem: \begin{align} (a) \quad & A\text{ at end} \;\Rightarrow\; A\text{ next to }B \\ (b1) \quad & \lnot(B\text{ next to }C) \\ (b2) \quad & \lnot(B\text{ at back end}) \\ (c) \quad & C\text{ at end} \;\Rightarrow\; \lnot(A\text{ next to }C) \\ (d1) \quad & B\text{ next to }D \;\lor\; \lnot(A\text{ next to }D) \\ (d2) \quad & \lnot(D\text{ at front end}) \;\Rightarrow\; D\text{ at back end} \\ \end{align} In addition to these, there are a number of rules about $\;\ldots\text{ next to }\ldots\;$ etc., like $$(0) \quad X\text{ at end} \;\equiv\; X\text{ at front end} \lor X\text{ at back end}$$ but for most of those formalization does not seem helpful.

Now the simplest reasoning I could find is as follows.


First note how $(d2)$ can quickly be simplified to $$ (d2') \quad D\text{ at end} $$ by rewriting $\;P \Rightarrow Q\;$ as $\;\lnot P \lor Q\;$ and simplifying using $(0)$.

Since $D$ is at one end by $(d2')$ and there are exactly four seats, we know that $A,B,C$ are sitting next to each other, and more specifically, by $(b1)$, $A$ sits inbetween $B$ and $C$. Therefore, by $(c)$ and contraposition, $C$ is not at the other end. Therefore $B$ must be at the other end, and by $(b2)$ that is the front end.

So the conclusion is that $B$ is at the front end, then $A$, then $C$, and finally $D$ at the back end.


Note we did not need to use $(a)$ and $(d1)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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