Paul Erdős’ favorite Problem

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s