Token Switching is a process for updating a set of black and white tokens. The process...

 

Transcribed Image Text:

Token Switching is a process for updating a set of black and white tokens. The process starts with a single black token. At each step, i. one black token can be replaced with two white tokens, or ii. if the numbers of white and black tokens are not the same, the colors of all the tokens can be switched: all the black tokens become white, and the white tokens become black. We can model Token Switching as a state machine whose states are pairs (b, w) of nonnegative integers, where b equals the number of black tokens, and w equals the number of white tokens. So the start state is (1,0). (a) Indicate which of the following states can be reached from the start state in exactly two steps: (0,0), (1,0), (0, 1), (1, 1), (0, 2), (2,0), (2, 1), (1,2), (0,3), (3,0) (b) Define the predicate F(b, w) by the rule: F(b, w) (b-w) is not a multiple of 3. Prove the following Claim. If F(b, w), then state (b, w) is reachable from the start state. (c) Explain why state (1167777,51088) is not a reachable state. Hint: Do not assume F is a preserved invariant without proving it. Token Switching is a process for updating a set of black and white tokens. The process starts with a single black token. At each step, i. one black token can be replaced with two white tokens, or ii. if the numbers of white and black tokens are not the same, the colors of all the tokens can be switched: all the black tokens become white, and the white tokens become black. We can model Token Switching as a state machine whose states are pairs (b, w) of nonnegative integers, where b equals the number of black tokens, and w equals the number of white tokens. So the start state is (1,0). (a) Indicate which of the following states can be reached from the start state in exactly two steps: (0,0), (1,0), (0, 1), (1, 1), (0, 2), (2,0), (2, 1), (1,2), (0,3), (3,0) (b) Define the predicate F(b, w) by the rule: F(b, w) (b-w) is not a multiple of 3. Prove the following Claim. If F(b, w), then state (b, w) is reachable from the start state. (c) Explain why state (1167777,51088) is not a reachable state. Hint: Do not assume F is a preserved invariant without proving it.