Solution. Number the coins 1 ... N, and let X = the number of the coin that is fake. Assume that you can determine the value of X in at most S steps. Then you can encode the value of X by means of recording answers to the weightings, producing a trinary number with at most S digits. Let us now choose the fake coin according to some probability distribution (so that X now becomes a random variable). Then our encoding scheme produces at most S bits all the time, and so the average wordlength for the code is at most S. From the theorem in the book (2.5.2), we conclude that H(X)/log(3) ≤ S. Now H(X) is maximal (=log N) if X is uniformly distributed, so we conclude that S ≥ log N/log(3) Conversely, you can just write down the scheme directly: split the coins into three groups, A1, A2, A3 so that A1 and A2 have equal number of coins, and each has approximately 1/3 of the total number of coins. Put A1 and A2 on the scales. With one weighting you can tell if the coin is in A1 (if A2 is heavier), A2 (if A1 is heavier) or A3 (if A1 and A2 are the same). But then you repeat the scheme using whichever group the coin is in; you get your answer when the final group has ≤ 3 coins. This clearly requires less than logN/log3 + 1 steps. Thus the answer is logN/log3.

Solution. Weigh simultaneously: 1 coin from bag 1; 10 coins from bag 2; 100 coins from bag 3 and so on (10^k coins from bag k). If all coins were genuine and you had n bags, you would get 10g + 100g + 1000g + ... + 10ⁿ⁺¹, so the total weight would have been the number 11....110 (as many 1's as you have bags, n+1 digits total). But if the k-th bag has fake coins in it, these coins would contribute 9×10^k rather than 10×10^k, so that the k-th digit would be zero, indicating which bag has fake coins (this works for all bags, except the first; if the first bag has fake coins in it, the least significant digit would be 9 rather than 0; you could avoid this exception if you were to add a 1g weight to the scales together with all the coins). There is no contradition with information theory, becase the output of your experiment is a number with as many digits as you want, so there is no limit to the number of scenarios (locations of bag with fake coins) that the outcome of the experiment can represent.

Solution. We first claim that xⁿ = 1 mod (x-1). This is easily seen by observing that x^n-1 is divisible by x-1. It follows that if p=a₀+a₁ x + ... + a_n-1 x^n-1, then p = a₀ + ... + a_n-1 mod (x-1). In other words, the remainder after division by x-1 of a polynomial p is the same as the sum of its coefficients. In the basis given by monomials, the matrix of this map is [ 1 1 ... 1 ]; you can also think of this map as giving you the parity (=sum of the digits) of the vector made from the coefficients of the polynomial. this map as

Solution.

(a) See problem E from last h/w.

(b) The data polynomial in this case is

The CRC is the remainder after dividing p by g = x³ + x + 1. Long division gives p ≡ 2x² mod g; since we are working over F₂, p ≡ 0 mod g and so the CRC is zero.

(c) Since g ≡ 1 mod (x - 1), it follows that if p ≡ r mod g, then p and r have the same remainder mod (x - 1). Indeed, if p ≡ r mod g, then p - r = hg, and so (p - r) ≡ h mod (x - 1) ⋅ g mod (x - 1) = g mod (x - 1). Thus the parity (sum of coefficients) of p and the CRC checksum r are the same; thus if we modify one coefficients of p (thus changing its parity) we must change the parity of r as well.

(d) If g were not irreducible, we would have g = fh. Since deg g = 3, it must be that one of deg h, deg f is at most 1 (since deg f + deg h = 3). Thus if g were not irreducible, g would have to be divisible by either x or x - 1. The remainder is 1 in each case.

To find the period, we list the remainders of various monomials mod g. You can see that the period is 7 (i.e., x⁷ - 1 is divisible by g, but x^k - 1 is not for any k < 7).

(e) If we change two bits, we alter p by x^a + x^b = x^a - x^b, where a,b are the locations of the changed bits. The CRC will be unchanged iff x^a - x^b is divisible by g. Let’s assume that a > b for definiteness. Then g must divide x^a - x^b = x^b(x^a-b - 1). Since g is irredicuble, it follows that g must divide either x^b or (x^a-b - 1). The former is clearly not the case. Thus g divides x^a-b - 1, which means that a - b (=distance between errors) is a multiple of the period, 7 in this case.

(f) Same argument as in (e)

(g) The period is 31, M=5.