Problem A: supper problem 1
   Consider the integers 1, 2, 3, ... 2n, and take any n+1 of them.
   Then there are two among these n+1 numbers which are relative prime.

Problem B: supper problem 2
   Consider the integers 1, 2, 3, ... 2n, and take any n+1 of them.
   Then there are two different among these n+1 numbers where on divides the other.

















SPOILER: pigeon-hole principle























Solution A:
   There must be two numbers which are only 1 apart,
   and hence relative prime.


Solution B:
  For each integer x in  [1,2n]  look at its "odd core".  That is, its largest
  odd factor;  i.e. the number (2k+1)  such that   x = (2k+1).2^j  .

  There are  n  possible odd cores:   1,3,5,7,...,(2n-1).
  So at least two must have the same odd core. (PHP)

  For these two, the smaller will divide the larger, the quotient being a 2-power.


Note:
  Both results are no longer true if one replaces n+1 by n:
  For this consider the sets {2, 4, 6, ..., 2n},
  respectively {n+1, n+2, n+3, ..., 2n}.


References:

- Martin Aigner, G\"unter M. Ziegler;
  Proofs from THE BOOK,
  Springer, Berlin, 1998
  - Chapter 20: Pigeon-hole and double counting
    Section 1: Numbers
    The two supper problems Erd\Hos asked Posa.

- P. Erd\Hos, proposer;  M. Wachsberger & E. Weiszfeld, M. Charosh, solvers;
  Problem 3739.  AMM 42 (1935) 396  &  44 (1937) 120.
  - n+1  integers from first  2n  have one dividing another.

- Paul Erd\Hos;
  The Mathematics Student 25 (Mai 1978) p2.   Proposer Erd\Hos.
  The Mathematics Student 26 (Jan 1979) p2-3. Solver Lai Lane Huey.
  - n+1  integers from first  2n  have one dividing another.

- Ross Honsberger;
  Mathematical Gems I,
  The Dolciani Mathematical Expositions No. 1
  The Mathematical Association of America, 1973
  (german: Mathematische Edelsteine, Vieweg, 1981)
  - chapter 2: Louis Posa
    supper problem A only

- I. S. Sominski;
  Die Methode der vollst\"andigen Induktion,
  Mathematische Sch\"ulerb\"ucherei Nr. 8,
  VEB Deutescher Verlag der Wissenschaften, Berlin 1954
  - Aufgabe 27 auf Seite 25-27,
    gibt den Schubfachbeweis und den Induktionsbeweis (kleinstes Gegenbeispiel)
    - n+1  integers from first  2n  have one dividing another.


Appendix:

Proof of B (by induction):
Proof by induction of the equivalent statement that given any n + 1 
numbers between 1 and 2n (integers all, of course) there must be two 
of them, say a and b such that a divides b.  Clear when n = 1.  
Suppose true for n.  Then look at n + 2 numbers between 1 and 2n + 2.
If n + 1 of them lie between 1 and 2n we are done.  Hence at most n 
of them lie between 1 and 2n, so we may assume that 2n + 1 and 2n + 2
are in the set of n + 2 numbers. In that case n + 1 is not is not in 
the set of numbers, since it is half of 2n + 2.  But then the set of 
numbers with 2n + 2 replaced by n + 1 has n + 1 of its members less 
than or equal to 2n, and so there are a and b in this collection such 
that a divides b.  One of these numbers obviously must be n + 1, and 
it must be the larger of them, but then the smaller of them divides
2n + 2.  I worked on this problem (it was either a homework problem 
or we were going through back Putnam exams or something like that) 
and I have to confess that I am not the one who saw his way to the 
end of the induction even though I felt pretty stupid after my 
partner in the enterprise saw it.

  -- "Achava Nakhash, the Loving Snake" <achava@hotmail.com>


--
http://www.mathematik.uni-bielefeld.de/~sillke/
mailto:Torsten.Sillke@uni-bielefeld.de