0

Five sticks (S1, S2, S3, S4 and S5) are placed next to each other, in a circular way so that S1 is next to S2, S2 is next to S3 and so on, and S5 is next to S1.

The sticks need to be painted black or white, such that each stick can be only painted one colour, and if two sticks are painted the same colour, they must be next to each other.

Solve this problem using propositional logic, or prove that it cannot be solved.

Here is my attempt:

These are the formulas I have come up with:

S1B → S2B (If S1 is painted black, S2 is also painted black)
S1W → S2W (If S1 is painted white, S2 is also painted white)
S2B → S3B 
S2W → S3W 
S3B → S4B 
S3W → S4W 
S4B → S5B 
S4w → S5w 
S5B → S1B 
S5W → S1W

I am not sure how to proceed from here. I think I need to combine these formulas into a single formula and show that it is a tautology (or not), but I seem to be stuck here.

Please help.

weak_at_math
  • 111

1 Answers1

2

Imagine that these $5$ letters wrap around like a circle as per your problem. Consider $3,4,5$ black sticks.

If there are $5$ black sticks $BBBBB$, clearly if you put these in a circle there are two that are the same color but they are not next to each other.

Same for the case of $4$ $B$'s, $BBBBW$. Just consider the two $B$'s separated by the $W$.

For the case of $3$ $B$'s, either the $B$'s are together like this: $BBBWW$, or the $W$'s are separated like this: $BBWBW$.

In the first case, clearly two $B$'s are separated by the middle $B$, so it does not satisfy the second condition. In the second case, the $W$'s are separated by a $B$ and the same issue occurs.

It has been shown that this does not work for the cases for $3,4,5$ black sticks. If one considers the cases for $0,1,2$ black sticks, this is the same as the cases for $3,4,5$ white sticks. As this argument is exactly the same as for $3,4,5$ black sticks, there is no such configuration that satisfies the required conditions.

Derek Luna
  • 2,732
  • 8
  • 19
  • Thanks a lot, that is a simple and clear answer. Just wondering, is this answer making use of propositional logic? The solution (or proof that it can't be solved) has to be done by making use of propositional logic. – weak_at_math Nov 20 '20 at 11:53
  • I can't imagine you'd be forced to prove this using only logical connectives and symbols in place of statements, perhaps I am missing something though. – Derek Luna Nov 20 '20 at 11:57
  • I want to add, that as written, I don't think your formulas are correct. Just because $S_{1}$ is black, doesn't necessarily imply that $S_{2}$ is black. All we know is that if two sticks are painted the same color, then they must be next to each other. This is not the same as the converse: If two sticks are next to each other then they must be the same color. – Derek Luna Nov 20 '20 at 12:01
  • Ok great, thank you! – weak_at_math Nov 20 '20 at 12:04
  • If what you meant was the converse, then the use of propositional logic is more clear: If $S_{i}$ for some $i$ is the statement that, say, $S_{i}$ is black, then there is an induction on $S$ where you see that $S{i}$ for all $i$ in the circle. This would mean that the only solutions are when the sticks are all the same color. – Derek Luna Nov 20 '20 at 12:05
  • You're welcome. – Derek Luna Nov 20 '20 at 12:06