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"
--
http://www.mathematik.uni-bielefeld.de/~sillke/
mailto:Torsten.Sillke@uni-bielefeld.de