It is said, that the following problem was Paul Erdős’ favorite problem.

The Problem:

Let n be any positiv whole number. Let n+1 numbers randomly be taken from the numbers 1 to 2n. Show that there will always exist two numbers x and y which are in the n+1 chosen numbers, so that x*z=y for some positive whole number z.

Solution:

It is possible to write every number in the form q*2^h for an uneven number q. If two numbers have the same q, one can always be devided by the other. It follows, that no two of the n+1 chosen numbers are allowed to have the same q. We know that there only exist n uneven numbers in the numbers from 1 to 2n. Since we need to choose n+1 numbers from this set, two numbers must have the same q when written in the form q*2^h.

This is a contradiction.

It follows that there will always be 2 numbers x and y with x*z=y for some positive whole z.

### Like this:

Like Loading...

*Related*