Proving an algorithm is correct for solving a game

1
votes

Given is a row of at most 30 stones which can either be black or white. No gaps are allowed at the start of the game, but there can be less than 30 stones. The goal is to remove all the stones. Only black stones can be removed, if a stone is removed, its neighbours change colours. If the stone removed was in the middle, this produces a gap that can't be filled any more; the neighbours of that stone are not considered neighbours after the stone is removed.

Now, I have created a program that solves this game using brute force. I have concluded that the game is only solvable if there are any black stones at all (obviously) and if the number of black stones is odd. Also, if the number of black stones is odd, the game can be solved by recursively removing the first black stone of the row.

My problem is I can't prove this condition that the number of black stones must be odd and that removing the first stone will solve the game. How can I correctly prove this algorithm?

I already tried to use induction, but I'm stuck:

Row(a,b) = a*black + b*white

RemoveFirstBlack(Row(1, b)) = RemoveFirstBlack(black + b*white) = 0 (if a=1 or n = 0 where a=2n+1 and n an integer)

Assume RemoveFirstBlack(Row(k*a, b)) = RemoveFirstBlack(k*a*black + b*white) = 0 with k = 2p + 1 and p an integer.

RemoveFirstBlack(Row((k+1)*a, b)) = RemoveFirstBlack((k+1)*a*black + b*white) = RemoveFirstBlack((2(p+1)(2n+1))*black + b*white) = RemoveFirstBlack(2(p+1)*a*black + b*white) = 0?

Thanks in advance for any pointers at all!

2
algorithmmathproofinduction
Using math and game theory. You can't find proof positive of anything by showing it's true for more and more examples. The best you could hope for would be a result that proved you wrong. – Alexander Corwin
@AlexanderCorwin, what do you mean? An inductive proof would be perfectly valid in this case. – aioobe
Isn't there a separate "Theoretical Computer Science" StackExchange site? – Charles Duffy
You mention gaps. If I remove a stone in the middle, is there now a gap separating two distinct rows? Are the neighbors of a stone I remove now considered neighbors? – Michael J. Barber
Thanks for your insights. I asked my question here because I believe algorithms are closely related to programming, and the correctness of the algorithm to the correctness of the program, but correct me if I'm wrong ;) @MichaelJ.Barber: if a stone in the middle is removed, there is a gap that can't be filled any more. So the neighbours of that stone are not considered neighbours after the stone is removed. – rbnvrw

2 Answers

2
votes

Assume we have a stone group that is solvable without splitting the group (if you must split the group then you actually have two groups that do not need split). Last stone to remove from the group must be single black [B]. The only way to get to [B] is through [WB], there is no other way. To get to [WB] you need either [BBB] or [WWB]. From here the pattern emerges. The only way to get to [xxW] is through [xxBB], and to get to [xxB] is through [xxWB]. In all these transitions the parity is unchanged, and final number of black stones is odd (one), so parity of a single non-splittable group must be odd.

Let's say that solution requires splitting a group to two non-splittable sub-groups. We already concluded that those two sub-groups must have odd parity. If we exclude the black stone that will make a transition to a new state those two groups actually have even number of blacks. If we add them, and add the black stone that will make the transitions we can conclude that a group that is solved by splitting it to two non-splittable groups must also have odd number of black stones.

Using induction on single-splitting groups we can conclude that any group must have odd number of blacks.

The solution to the original problem does not require brute force. Just pick the first black stone that you come along.

2
votes

I suggest you try to treat two moves as one. (I.e. that the 30 stones are removed in 15 moves.)

This would allow you to show that the property of having an odd or even number of black stones is invariant throughout the game. A proof sketch follows:

Base cases: Two stones left. Odd number of blacks. Both stones can be removed in one double-move:

b w       -> _ b        ->  _ _
w b       -> b _        ->  _ _

For four stones or more, list the various different possible prefixes where O and E stands for a suffix-sequence of stones with an odd and even number of blacks respectively.

Here's two cases to get you started:

b b w b E  -> _ w b b E  ->  _ w _ w E
b b w w O  -> _ w b w O  ->  _ b _ b O
....

In each case you note that the resulting sequence (_ w _ w O for instance) contains an odd number of blacks.

Since if a sequence consists of one stone, and the number of stones is odd, then that single stone must neccesarily be black, which means that also the last stone can be removed.

Noticed that you also wanted to show that it was impossible if there was an even number of black stones. This is just as easy. The base cases (b b and w w) are impossible to solve and since each double-move removes an even number of black stones, you're out of luck if you start with an even number :-)