Given any 6 integers from 1 to 10, some two of them have an odd sum.

Solution


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

Copyright © 1996-2018 Alexander Bogomolny

Given any 6 integers from 1 to 10, some two of them have an odd sum.

It is a special case of:

Given more than half the elements of a finite quasigroup G, every element of G is the product of two of the given elements.

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

    71470986