It is a special case of:
RemarkQuasigroup G is a groupoid in which, for every a and b, equation ax = b and xa = b have unique solutions which are not necessarily equal unless the associative law holds. From here it follows that in the multiplication table for a finite quasigroup each element appears only once in every row and in every column. So that columns and rows in such a table are permutations of, say, the first row. Tables with this property are known as Latin Squares. Conversely, The set of symbols in a latin square is a finite quasigroup when that square is interpreted as a multiplication table for the symbols it contains.
Let A be the given subset of the quasigroup G. Let x be an element of G. In the multiplication table of G every element appears exactly once in every row and column. Let f(x) be the number of times that x appears in the table as the product of elements of A. Then, in the subtable consisting of those rows labelled by an element of A and the columns not labelled by elements of A, the element x appears |A| - f(x) times. Hence, in the subtable consisting of those rows not labelled by elements of A and columns not labelled by elements of A, the element x appears |G| - |A| - (|A| - f(x)) = |G| - 2|A| + f(x)≥0 times. Since |G| - 2|A| < 0, it follows that f(x) > 0; so x is the product of two elements of A (perhaps the square of an element of A).
|Date:||Mon, 2 Oct 2000 00:06:06 +0300 (EET DST)|
Dear Alexander Bogomolny,
In the problem: "Given any 6 integers from 1 to 10, some two of them have an odd sum" there is a much simpler solution:
To start with, two integer numbers have an odd sum if and only if one of them is odd and the other is even. From 1 to 10, there are 5 odd and 5 even integers. So in 6 numbers taken from 1 to 10 there is at least one odd and one even number, because of the pigeonhole principle. So there is at least one pair of numbers that have an odd sum.
I really enjoy "cut-the-knot"