Imagine a rectangle divided into 3x4 squares, and put a digit in each square.

     +---+---+---+---+
     | a | b | c | d |  A
     +---+---+---+---+
     | e | f | g | h |  B
     +---+---+---+---+
     | i | j | k | l |  C
     +---+---+---+---+
       D   E   F   G

The number abcd is denoted by A, that is, A = 1000a + 100b + 10c + d, and the same for the other 2 horizontal numbers B and C.

The number aei is denoted by D, that is, D = 100a + 10e + i, and the same for the other 3 vertical numbers E, F and G.

Prove that if any 6 of these numbers (A, B, C, D, E, F, G) are divisible by 7, then the last number must also be divisible by 7.

10 is congruent to 3 mod 7.
100 is congruent to 2 mod 7.
1000 is congruent to 6 mod 7.

We are only concerned with the congruences mod 7, so only the value of the digits mod 7 need be considered.  For example, it doesn't matter whether a is 1 or 8 as it's only a difference of 7000, which is divisible by 7, and either way its value to the overall congruence of ABCD is 6. Similarly if a were 2 or 9, it would be worth 5 either way.

In testing the hypothesis for, say, all the rows and the first three columns, a, b and c determine what d must be to satisfy one of the premises. Likewise e, f and g determine h, and similarly for the last row.  For the columns, a and e determine i, etc. 

In this particular case, l can be determined from either the previously determined d and h, or the previously determined i, j and k. If they don't agree, the hypothesis is disproved.

The following program, for all combinations of a, b, c, e, f and g, determines the necessary d, h, i, j and k.  It then sees if the l value derived from d and h is equal to the l value derived from i, j and k. If the l values are not equal, that is reported. Capital letters are used for the variables due to UBASIC syntax; not to be confused with the capitals in the puzzle statement.

   10   for A=0 to 6
   20   for B=0 to 6
   30   for C=0 to 6
   40   for E=0 to 6
   50   for F=0 to 6
   60   for G=0 to 6
  100   D=(14-(6*A+2*B+3*C)@7)@7
  110   H=(14-(6*E+2*F+3*G)@7)@7
  130   I=(14-(2*A+3*E)@7)@7
  140   J=(14-(2*B+3*F)@7)@7
  150   K=(14-(2*C+3*G)@7)@7
  160   L1=(14-(2*D+3*H)@7)@7
  170   L2=(14-(6*I+2*J+3*K)@7)@7
  180   if L1<>L2 then
  190     :print A;B;C;D:print E;F;G;H:print I;J;K:print
  999   next:next:next:next:next:next

For all 117,649 combinations of a, b, c, e, f and g, no discrepancy is found.

At first glance this would indicate we've only checked one case, or rather two cases: where the right column (G) was the dependent one, or the bottom row (C) was.

However, 7 is a prime number, making it, in particular, relatively prime to 6, 2 and 3, the coefficients of the digits used in adding up the values of the entire 3- or 4-digit numbers mod 7.  As a result, there is a 1-to-1 correspondence between, say, the needed a values and the needed d values to make ABCD = 0 mod 7. So if, say, column 7 is a known multiple of 7, each digit there determines, along with the middle two columns, what column a is. And we have already determined that combinations of the first 3 columns determine the rest.

In fact, this property was already used in our indifference as to whether the "remaining" number was the bottom row or the right-hand column. In either case it did not matter what column/row (respectively) was used as the test for compatibility.

 

Posted by Charlie on 2008-11-04 13:19:14