Let a and b be positive integers, with a < b < 2a. Then, given more than half of the integers in the set {1, 2, ..., a + b}, some two of the given integers differ by a or by b.

Solution


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

Copyright © 1996-2018 Alexander Bogomolny

Let a and b be positive integers, with a < b < 2a. Then, given more than half of the integers in the set {1, 2, ..., a + b}, some two of the given integers differ by a or by b.

The proof is by William A McWorter Jr.

Form the array below.

123...bb+1b+2b+3...a+b
a+1a+2a+3...a+b123...a

There are a + b columns and each integer appears exactly twice in the array. Now, given more than half the integers in {1, 2, ..., a + b}, the given integers appear in the above array, counting multiplicity, more than a + b times. Hence there must be two occurrences of the given integers in the same column. Thus those occurrences differ by a or b.

The reason for the condition b < 2a is that you need only a little over a third of the integers if b = 2a. And the original proof still works if b > 2a.


Related material
Read more...

  • 17 rooks on a Chessboard
  • Chinese Remainder Theorem
  • Pigeonhole in a Chessboard
  • Pigeonhole in Concurrent Cuts
  • Monochromatic Rectangle in a 2-coloring of the Plane
  • Polynomial and Integer Division
  • Power of three that ends with 001
  • Pigeonhole Principle (subsets)
  • Four Numbers, Six Differences, GCD of the Products

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

    Copyright © 1996-2018 Alexander Bogomolny

    71493806