Problem:
   The integers from 1 to 2*n are in a box. 
   For all a and b, if a divides b, either a or b 
   has to be thrown out of the box.
   Prove that you can't keep more than n integers in the box. 










SPOILER


From - Fri Oct 30 14:26:26 1998
From: mathwft@math.canterbury.ac.nz (Bill Taylor)
Newsgroups: sci.math
Subject: Re: Number theory quickie
Date: 30 Oct 1998 07:42:02 GMT


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 if you keep (n+1) in the box, 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.

Ta-Dah!
-------------------------------------------------------------------------------
            Bill Taylor             W.Taylor@math.canterbury.ac.nz
-------------------------------------------------------------------------------

Bill,

I like your proof better than the one I am now trying to remember, but here
goes anyway.  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>


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.
    The second one is not mentioned in:
    Ross Honsberger, Mathematical Gems 1, MAA, chapter 2: Louis Posa
    The second supper problem is the problem in question.

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

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