Problem 1. Let a and b be positive integers.
(a) What are the possible smallest nonnegative remainders when a is divided by 6?
(b) What are the possible smallest nonnegative remainders when a 2is divided by 6?
(c) Show that if a 2 + b2 is divisible by 7, then both a and b are divisible by 6.
(d) Does the result in part (c) hold for any positive integers other than 6?
Problem 2. The telephone numbers in a town run from 00000000 to 99999999. The new automated
switchboard may transpose two digits which have exactly four other digits between them, but makes no
other kinds of errors. How should a tenth digit be added to each telephone number so that no wrong numbers
will be reached because of a switching error?
Problem 3. Given the following set of code words
c1 = 0 1 1 0 0 0 c 2= 0 0 1 1 1 0 c 3 = 0 1 0 1 1 1 c 4= 0 1 1 0 1 1
c5 = 1 1 0 0 1 1 c 6= 1 0 1 1 0 1 c 7 = 1 1 0 1 0 0 c 8= 1 1 1 0 0 0
(a) Find the Hamming distance between each pair of code words. What is the minimum Hamming distance
between code words?
(b) Explain how it is possible to detect up to two transmission errors using this code. Give an example to
(c) Explain how it is possible to correct up to one transmission error using this code. Give an example to
(d) Show that no decoding scheme can both correct all single errors and detect all double errors, that is,
show that there must be code words a and b and a received word r such that r comes from a via one
error and from b via two errors.
Problem 4. The following Hamming coded number was received. Correct the number if it is not correct.
a a a a a a a a
b b b b b b b b
c c c c c c c c
d d d d d d d d
0 0 0 1 1 1 0 1 1 0 1 0 1 1 1
Problem 5. A Coffee Club with 9 members meets every Monday, Wednesday and Friday at Caf´e Rendevous.
At each meeting, 5 members sit at a table indoors and the other 4 outdoors. Is it possible, in the course of
a week, for each member to be indoors at least once and outdoors at least once, and be at th