MHB Logic Exercise: Solving a Canoe Team's Seating Arrangement Dilemma

[Casual]

Here I am with another problem... :)
It's from a Discrete Mathematics course and it requires a step by step proof with logical equivalences and deductions made based on the laws of logic.

A,B,C and D are all on the same canoe team. They don't know what sitting order they should make and all of them have a certain wish. Could they find a sitting arrangement that satisfies all their wishes?
A: I'd like to sit at the back only if I sit next to B.
B: I don't want to sit next to C and I don't want to sit at the back.
C: If I sit at the back, I don't want to sit next to A.
D: I want to sit next to B or not next to A, and if I can't sit at the front, then I want to sit at the back.

I need help with getting started. I can attack the problem verbally(so to speak). I can provide an arrangement which would fulfill every wish. It's C A B D, C being at front and D being at the back. However, in my course this proof wouldn't be good enough, and therefore I need to provide a more rigorous one. Any suggestions? I was thinking of making a statements for every possibility, but proving it that way seems tiresome and redundant... Just tell me in which direction I should head, and I'll give it a go on my own.

 

[Evgeny.Makarov]

For now I can only say that, in addition to C A B D, B A C D also seems to work (found by brute-force search using the computer).

 

[Casual]

How about this. Since the question is whether there is a way for them to sit, fulfilling everyone's wishes, it would mean that it's enough to prove that such a sitting order exists.

Let A,B,C,D be numbers from and 1 to 4, representing the positions of the team members, 1 being the front and 4 being the back.

A:I want to sit at the back only if I sit next to B. This transcribes into: if (A=4) then (B=3).
B:I don't want to sit next to C and I don't want to sit at the back. This transcribes into: (B=/=4) and (B=/=C+1) and B(=/=C-1).
C:If I sit at the back, I don't want to sit next to A. This transcribes into: if (C=4) then (A=/=3).
D:I want to sit next to B or not next to A, and if I can't sit at the front then I want to sit at the back. This transcribes into: (D=B+1 or D=B-1 or D=/=A+1 or D=/=A-1) and (if D=/=1 then D=4.

Now, if we join all of these into one statement including the existential quantifier we get:

∃A∃B∃C∃D( [(A=4) -> (B=3)] ^ [(B=/=4) ^ (B=/=C+1) ^ (B=/=C-1)] ^ [(C=4) -> (A=/=4)] ^ [((D=B+1) v (D=B-1) v (D=/=A+1) v (D=/=A-1)) ^ ((D=/=1) -> (D=4))] )

In order to prove this we need to provide at least one example for which the formula is satisfied. That's how we deal with existential quantifiers in my book.
Would this be a viable solution?

 

[Evgeny.Makarov]

D:I want to sit next to B or not next to A, and if I can't sit at the front then I want to sit at the back. This transcribes into: (D=B+1 or D=B-1 or D=/=A+1 or D=/=A-1) and (if D=/=1 then D=4.

"D=/=A+1 or D=/=A-1" should be replaced by "(D=/=A+1 and D=/=A-1)," and similarly in the final formula. Otherwise I agree with what you said.

 

[toteto]

I think that this problem has two solutions.
< | | | | > - my awesome canoe with 4 sits.
end < D|B|A|C >
end < D|C|A|B >

I solved it drawing 4 tables with 4 columns in it and writing who wants to sit where and based on what.

The biggest problem i had with A, trying to locate him at the end when i saw that he does't need to sit at the back even if he sits next to B.

Also if you would like to send this answer as final, pm me to tell you what to write so our answers are not the same.

 

[steff]

Hi Casual.
I'm taking the same course (FINKI right?).

I don't think that you understand/translate the problem correctly.

In the statements from B and D you have "first" and "last", meaning position 1 and 4.
In the statements from A and C you have "at the end", meaning position 1 or 4, not just 4.

The only solution for this problem is:
< 1|2|3|4 >
< B|A|C|D >