18.310 Assignment 1   Due Monday, September 13, 2004


1. Verify that one can have a good non-adaptive scheme for  n = 9 through 13 coins; by producing a three-row matrix without a good coin having n columns, obeying the conditions that rows have 0 sums, and no columns the same or negative of one another; for each of these values of n.

hint: you can without great effort produce 4 groups of 3 columns each, so that each group of 3  sums to 0; and also the all 0 column; these handle 9, 10, 12 and 13 coins. to get the 11 case you may take the 12 solution, add the missing column and omit two rows that add up to it.

you can do this any other way if you want.


2. Construct a 4 weighing optimum scheme with the maximum number of coins including one good coin using the procedure described. This can be done on a spreadsheet or on paper. It is easy on a spreadsheet.


3. Build a 4 weighing automatic spreadsheet bad coin finder. It should have a column for each potentially bad coin, indicating its number and when it is to go on the balance.

If you enter a  (0,1,-1) column of length 4, it should tell you which coin is bad and if it is heavy or light.

(I use the if, or and sum functions on the spreadsheet to do this.)  

You may write a little program to do this instead.