Solution

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

It is a special case of:

Remark

Quasigroup 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.

Proof

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).

Subject:	Pigeonhole/quasi.html
Date:	Mon, 2 Oct 2000 00:06:06 +0300 (EET DST)
From:	Odysseas Galanis

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"
Yours,
Odysseus Galanis

Related material Read more...
	Pigeonhole Principle (Same sum)
	Pigeonhole in a Matrix
	Pigeonhole in Calendar
	A nice puzzle modeled on the Petersen graph
	Proizvolov's identity in a game format
	Pigeonhole with Disjoint Intervals
	All antichains
	Euclid via Pigeonhole
	Light Bulbs in a Circle (an Interactive Gizmo)
	Seven integers under 127 and their Ratios

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny