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

Home > Logic
Red, White, and Blue (Posted on 2015-07-29) Difficulty: 3 of 5

  
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 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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


Private Sub Form_Load()
 Form1.Visible = True
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)

 red = 3: white = 4: blue = 5
 hadstate(red, white, blue) = 1
 
 makeMove
 
 Text1.Text = Text1.Text & crlf & crlf
 
 For red = 0 To 12
 For white = 0 To 12
 For blue = 0 To 12
   If hadstate(red, white, blue) Then
     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
       hadstate(red, white, blue) = 1
       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 B
2 3 7     b
1 2 9     bb
0 1 11    bbb
2 0 10    bbbr
0 4 8     bbw
3 1 8     bbr
5 0 7     bbrr
4 2 6     bbrrw
6 1 5     bbrrwr
5 3 4     bbrrwrw
4 5 3     bbrrwrww
3 7 2     bbrrwrwww
2 6 4     bbrrwrwwwb
1 5 6     bbrrwrwwwbb
0 7 5     bbrrwrwwwbbw
1 8 3     bbrrwrwwwbw
0 10 2    bbrrwrwwwbww
2 9 1     bbrrwrwwwbwwr
1 11 0    bbrrwrwwwbwwrw
4 8 0     bbrrwrwwwbwwrr
5 6 1     bbrrwrwwwr
7 5 0     bbrrwrwwwrr
6 4 2     bbrrwrwwwrrb
8 3 1     bbrrwrwwwrrbr
7 2 3     bbrrwrwwwrrbrb
9 1 2     bbrrwrwwwrrbrbr
8 0 4     bbrrwrwwwrrbrbrb
11 0 1    bbrrwrwwwrrbrbrr
10 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information