All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Red, White, and Blue (Posted on 2015-07-29)

A bag contains 3 red, 4 white, and 5 blue balls. Two balls of different
color are removed from the bag and replaced with two balls of the third color.

Prove that no matter how many times this procedure is repeated, it is impossible for all twelve balls in the bag to be the same color.

 See The Solution Submitted by Bractals Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer proof | Comment 1 of 4
The program below makes all possible sequences of moves, recursively seeking all possible states of the system. The first time through a given set of numbers of red, white and blue balls it continues with all possibilities from there; the second time it reaches the same set, it does not continue, as the possibilities starting from there have already been exhausted.

DefDbl A-Z
Dim crlf\$, hadstate(12, 12, 12), red, white, blue, h(50), lvl

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

red = 3: white = 4: blue = 5

makeMove

Text1.Text = Text1.Text & crlf & crlf

For red = 0 To 12
For white = 0 To 12
For blue = 0 To 12
Text1.Text = Text1.Text & red & Str(white) & Str(blue) & crlf
DoEvents
End If
Next
Next
Next

Text1.Text = Text1.Text & crlf & " done"

End Sub

Sub makeMove()
For a = 1 To 2
For b = a + 1 To 3
c = 6 - a - b
Select Case c
Case 1
red = red + 2
white = white - 1
blue = blue - 1
Case 2
white = white + 2
red = red - 1
blue = blue - 1
Case 3
blue = blue + 2
white = white - 1
red = red - 1
End Select

If red >= 0 And red <= 12 Then
If white >= 0 And white <= 12 Then
If blue >= 0 And blue <= 12 Then
If hadstate(red, white, blue) = 0 Then
lvl = lvl + 1
h(lvl) = c
Text1.Text = Text1.Text & red & Str(white) & Str(blue) & "     "
For mno = 1 To lvl
Text1.Text = Text1.Text & Mid("rwb", h(mno), 1)
Next mno
Text1.Text = Text1.Text & crlf
makeMove
lvl = lvl - 1
End If
End If
End If
End If

Select Case c
Case 1
red = red - 2
white = white + 1
blue = blue + 1
Case 2
white = white - 2
red = red + 1
blue = blue + 1
Case 3
blue = blue - 2
white = white + 1
red = red + 1
End Select

Next
Next
End Sub

The only reachable states are shown below with the sequence of moves needed to get there. Each step of the sequence is indicated by the starting letter of the color that gained two balls in the process of that step:

`R W B2 3 7     b1 2 9     bb0 1 11    bbb2 0 10    bbbr0 4 8     bbw3 1 8     bbr5 0 7     bbrr4 2 6     bbrrw6 1 5     bbrrwr5 3 4     bbrrwrw4 5 3     bbrrwrww3 7 2     bbrrwrwww2 6 4     bbrrwrwwwb1 5 6     bbrrwrwwwbb0 7 5     bbrrwrwwwbbw1 8 3     bbrrwrwwwbw0 10 2    bbrrwrwwwbww2 9 1     bbrrwrwwwbwwr1 11 0    bbrrwrwwwbwwrw4 8 0     bbrrwrwwwbwwrr5 6 1     bbrrwrwwwr7 5 0     bbrrwrwwwrr6 4 2     bbrrwrwwwrrb8 3 1     bbrrwrwwwrrbr7 2 3     bbrrwrwwwrrbrb9 1 2     bbrrwrwwwrrbrbr8 0 4     bbrrwrwwwrrbrbrb11 0 1    bbrrwrwwwrrbrbrr10 2 0    bbrrwrwwwrrbrbrrw`

All the possible states in a sorted sequence, including the initial state:

0 1 11
0 4 8
0 7 5
0 10 2
1 2 9
1 5 6
1 8 3
1 11 0
2 0 10
2 3 7
2 6 4
2 9 1
3 1 8
3 4 5
3 7 2
4 2 6
4 5 3
4 8 0
5 0 7
5 3 4
5 6 1
6 1 5
6 4 2
7 2 3
7 5 0
8 0 4
8 3 1
9 1 2
10 2 0
11 0 1

Of course, for example, bbrrwrwwwb is the hard way to get to (2,6,4), where merely w would get there right away. It's just that the algorithm explores all sequences starting with b first. (Why b? It actually chooses which to decrease, and starts with r and w.)

None of these states have 12 of one color and zero of each of the other two.

 Posted by Charlie on 2015-07-29 14:35:28

 Search: Search body:
Forums (2)