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
180 if L1<>L2 then
190 :print A;B;C;D:print E;F;G;H:print I;J;K:print
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