Transcript Exercise 2 & Keys ()

Exercise 2 for Proof Techniques
(Key answers are in the following slide.)
1. Prove that a = b if and only if a  b and a  b.
2. Show that the numbers appearing on columns and rows of 2 x 2 bit matrix doe not exhaust all possible binary
numbers of length 2.
3. Spener’s lemma claims the following: Suppose that there is a linear array of n  2 nodes, each labeled with
either 1 or 2 as the following figure illustrates. Let two adjacent nodes with different labels (i.e., either 2-1 or 1-2)
call “good label block.” If the two end nodes are assigned with different labels, then whichever way the other
nodes are assigned with the labels, the number of good label blocks is always odd.
1
1
1
2
1
. . . . . . .
2
Good label blocks
(a) Prove Sperner’s lemma by induction.
(b) Can we claim the same property if we define the good label block as a block having identical label?
Justify your answer.
4. There once lived a king, named Hagar, who had thousands of sons and daughters, still giving more births to his
wives. One of his serious problems was to give a new (unique) name to his every new born baby. One day he
summoned one of his royal advisers who is in charge of information processing, and ordered to find an efficient
idea.What will this adviser’s idea be, if he attended our classes, where proof techniques have been discussed?
Your answer should be clear and complete. You may use any assumption, if needed.
Key answers for Exercise 2:
1. The problem is to prove the following:
(a) if a = b, then a  b and a  b
(b) if a  b and a  b, then a = b
Proof (a). If a = b, then obviously both expression a  b and a  b are true.
(b) If both a  b and a  b are true, then it implies a = b.
2. We will show that in 2  2 bit matrix, it is impossible to put 4 different binary numbers of length 2 in the
two columns and two rows. It is enough to show that whichever way you put the bits, there appear at least
tow identical binary numbers. Let a, b, c and d be a bit (either 0 or 1) at each entry as shown in Figure (a).
We can observe the following: Entries b and c cannot be same. Otherwise row 1 and column 1 will have
the same number ab = ac.
So suppose that b = 1 and c = 0. (We can apply the same argument for the case of b = 0 and c = 1.)
Then matrix will contain the following numbers:
a1 in row 1 and a0 in column 1.
0d in row 2 and 1d in column 2.
Can we make 4 different numbers by assigning a binary value to a and d?
1
2
1
a
b
2
c
d
The answer is no. If a = 0, then row 1 and column 1, respectively, will have 01 and 00.
If d = 0, then row 2 will have the same number 00 as column 1. If d = 1, then row 2
will have the same number 01 as row 1. We can argue similarly for the case when a = 1.
Figure (a)
Answer 3-(a) Proof of the Sperner’s lemma
(1) Induction Base: when the number of nodes n = 2; Obviously the number of good block is one, which is odd.
1
2
(2) Hypothesis: Suppose that, for any number of nodes n’ < n, the number of good blocks is odd.
(3) Induction : We prove that when the number of nodes is n’+ 1 = n, the number of good blocks is also odd.
We examine the problem divided in two cases depending on the label of n’-th node.
1
2
1
?
. . . . . . .
n’ n’+1
?
2
Case 1: When the label of node n’ is 2 (see the figure below). According the the hypothesis, the first n’
nodes has odd number of good blocks, and the last block is not a good block. Hence, total number of good blocks is
odd.
1 2
. . . . . . .
n’ n’+1
1
?
2
2
Case 2: When the label of node n’ is 1 (see the figure below). Since the last block is a good block, it is
enough to prove that in the array of first n’ nodes there are even number of good blocks. Going to the left from n’-th
node, find the first node whose label is 2 (see the figure below). If there is no such node, then the number of good
blocks to the left of node n’ is zero, which is even.
If there is a node with label 2 (say, in i-th node), then according to the induction hypothesis, the array of first i
nodes has odd number of good blocks, and between i-th and i+1st node there is another good block. Hence the number
of good blocks in the first n’ nodes is even. We are all done.
1
2
. . . i . . .
1
?
2
1
n’ n’+1
1
2
Answer 3-(b): (This problem appears in homework 1.)
Answer 4: There can be many solutions for the problem with some encoding techniques. Another simple
idea could be using the diagonalization technique to make a new name from the current list of names.