Error Detection and Correction:Nim; Secure Communication; RAIDGreg PlaxtonTheory in Programming Practice, Fall 2005Department of Computer ScienceUniversity of Texas at AustinThe Game of Nim• Initially, there are a number of piles of chips• Two players move alternately• A legal move consists of removing a positive number of chips fromsome pile• The first player who cannot make a legal move loses• Thus, the player who removes the last chip winsTheory in Programming Practice, Plaxton, Fall 2005A Winning Strategy for Nim?• A state is losing if the player to move next can be forced to lose:– Examples: (1) The state in which all piles are empty; (2) Any statewith an even number of nonempty piles, each of which has exactlyone chip; (3) Any state with two piles of equal size• A state is winning if the player to move next can force a win– Examples: (1) Any state with exactly one nonempty pile; (2) Anystate with an odd number of nonempty piles, each of which hasexactly one chip; (3) Any state with two piles of unequal size• Is every state either losing or winning or could there be “uncertain”states?Theory in Programming Practice, Plaxton, Fall 2005Every State is Either Losing or Winning• Proof by strong induction on the total number of chips• Base case: If there are no chips, the state is losing• Induction hypothesis: Let k be a nonnegative integer and assume thatevery state with a total of at most k chips is either losing or winning• Induction step:– Let S be an arbitrary state with a total of k + 1 chips– By the IH, every state reachable via a legal move from S is eitherlosing or winning– If every state reachable via a legal move from S is winning, then Sis losing; otherwise, it is winningTheory in Programming Practice, Plaxton, Fall 2005Towards a Characterization of Losing/Winning States• Earlier we saw that if every pile has 0 or 1 chips, then the parity ofthe number of nonempty piles determines whether a state is losing orwinning• Conjecture: A state is losing iff, for all nonnegative integers i, an evennumber of piles have the property that the binary representation of thenumber of chips in the pile has a 1 in bit position i• What is a more succinct statement of this conjecture?Theory in Programming Practice, Plaxton, Fall 2005Bad and Good States• For any state S, let f (S) denote the XOR of the pile sizes• A state S is bad if f(S) = 0, and good otherwise• Theorem: A state is losing (resp., winning) iff it is bad (resp., good)• In order to prove this claim, we will establish two lemmas– Lemma 1: Any legal move executed in a bad state yields a goodstate– Lemma 2: For any good state, there exists a legal move to a badstate• Why does the theorem follow?Theory in Programming Practice, Plaxton, Fall 2005Proof of the Theorem (using Lemmas 1 and 2)• Proof by strong induction on the total number of chips• Base case: If there are no chips, the state is losing and bad• Induction hypothesis: Let k be a nonnegative integer and assume thatevery bad (resp., good) state with at most k chips is losing (resp.,winning)• Induction step: Let state S have a total of k + 1 chips– If S is bad, then by Lemma 1, every state reachable via a legal movefrom S is good, and by the IH, winning; hence, S is losing– If S is good, then by Lemma 2, there is a legal move from S to astate that is bad, and by the IH, losing; hence, S is winningTheory in Programming Practice, Plaxton, Fall 2005Proof of Lemma 1• Lemma 1: Any legal move executed in a bad state yields a good state• Suppose we are in a bad state S and we move to a state S0by reducingthe number of chips in some pile from x to y• Let i be a bit position where x has a 1 and y has a 0– Such an i exists since x > y• Note that bit position i of f(S0) is 1, so S0is goodTheory in Programming Practice, Plaxton, Fall 2005Proof of Lemma 2• Lemma 2: For any good state, there exists a legal move to a bad state• Let S be an arbitrary good state• Let i be the highest bit position of f(S) containing a 1• Let A be an arbitrary pile for which the number of chips, denoted byx, has a 1 in bit position i of its binary representation– Such a pile A exists since bit position i of f(S) is 1• Note that x ⊕ f(S) < x and (x ⊕ f(S)) ⊕ (x ⊕ f(S)) = 0, so we canreach a bad state by reducing the number of chips in A from x tox ⊕ f(S)Theory in Programming Practice, Plaxton, Fall 2005Secure Communication: A Simple Approach• Suppose a sender wishes to securely send a block of data x to a receiverover an insecure communication channel• Let us call a block of data random if each bit is independently set to 0(resp., 1) with probability12• Suppose the sender and receiver share a secret random block(sometimes called a key) k• The sender sends y = x ⊕ k over the channel• Note that the block y is random!– Therefore an eavesdropper gains no information whatsoever aboutthe message x from observing yTheory in Programming Practice, Plaxton, Fall 2005Disadvantages of this Approach• Key exchange problem: The sender and receiver need to agree inadvance on the random block k, which must be sent over a securechannel• The key should not be reused– For example, suppose the eavesdropper sees x1⊕ k and x2⊕ k– The eavesdropper can calculate x1⊕ x2, which is (presumably) notrandom and might yield statistical clues towards partially decipheringthe content of x1and x2– Furthermore, an eavesdropper who knows the content of a singleblock can determine k and thereby decipher all blocks• Later in the course we will see a much better solution to the problemof secure communicationTheory in Programming Practice, Plaxton, Fall 2005Fault-Tolerant Storage• Suppose the records of a large corporate database are to be stored ona collections of disks• Occasionally one of the disks fails• We would like to store the data in such a way that the entire contentof the database can be recovered whenever any single disk fails• Naive solution:– Store two copies of each record (on different disks)– This doubles the storage requirement• A better solution?Theory in Programming Practice, Plaxton, Fall 2005Redundant Array of Independent Disks (RAID)• Store the database nonredundantly on k disks• Use one additional disk to store the XOR of these k disks– Here we are viewing the content of each disk as a block of bits• If any disk fails, its content can be recovered since it is the XOR of