Transcript Carom 1-12: Multiple

www.carom-maths.co.uk
Activity 1-12 : Multiple-free sets
Let’s call a set of numbers multiple-free
if there is no pair of numbers in the set
such that one is a multiple of the other.
So { 3, 4, 5} is multiple-free, while
{ 3, 4, 6} is not.
Task: you are given the
whole numbers from 1 to 20.
What is the largest multiple-free set
of these you can pick?
The primes?
{19, 17, 13, 11, 7, 5, 3, 2}
8 numbers.
If we take off 2 and 3,
and add some others...
{19, 18, 17, 13, 12, 11, 8, 7, 5}
9 numbers.
Or we could take the top half...
{19, 18, 17, 16, 15, 14, 13, 12, 11}
10 numbers.
Conjecture:
if we pick n + 1
of the numbers from 1 to 2n,
this set will never be
multiple-free.
Call this statement Sn.
Task: prove Sn
for all n  1.
So S5 says:
if we pick 6 of the numbers from 1 to 10,
this set will never be multiple-free.
So S14 says:
if we pick 15 of the numbers from 1 to 28,
this set will never be multiple-free.
So S105 says:
if we pick 106 of the numbers from 1 to 210,
this set will never be multiple-free.
And now for something apparently unrelated...
Task: you are given a 2 by 2 square,
and you are asked to pick five points.
Prove that two of the points
must lie within √2 of each other.
This looks tough initially,
but The Pigeon-hole Principle
makes it easy.
What does this say?
If you have n + 1 letters
and n pigeon-holes to post them into,
then some pigeonhole
must contain at least two letters.
This sounds obvious, but it is a wonderfully useful
tool for proving all sorts of things.
Task: we know n people enter a room
and some handshakes take place.
No one shakes their own hand!
Show that there is always some pair of people
who have shaken hands the same number of times.
Could The Pigeon-hole Principle help us here?
There are two cases:
1. Someone shakes everybody else’s hand
2. Nobody shakes everybody else’s hand
If somebody shakes everybody else’s hand, then
the possible handshake-scores around the room
are 1, 2, ..., n  1.
No one can score 0, since everybody’s hand has been shaken.
We have n  1 possible scores and n people, so by
the Pigeon-hole Principle, two people have the same score.
If nobody shakes everybody else’s hand, then
the possible handshake-scores around the room
are 0, 1, 2, ..., n  2.
Once again we have n  1 possible scores and n people,
so by the Pigeon-hole Principle,
some two people have the same score.
Let’s return to our five points problem.
Divide the square
into four equal ones.
We have to pick five points, so by the Pigeon-hole Principle,
two must be in the same square.
The furthest apart that two points
in the square can be is √2, so we are done.
Returning to our original problem...
Proof: Every integer can be written as 2uv,
where v is odd, and u  0.
So we can write the 2n numbers in this form,
a power of 2 times an odd number.
So we write the 2n numbers in this form,
2uv,
where v is odd, and u  0.
Now pick n + 1 numbers from these 2n numbers.
There are only n possibilities for v,
so we must (by the Pigeon-Hole Principle)
pick two numbers with the same v.
But 2pv always divides 2qv, if q > p,
so we now have a pair in our set where
one number divides the other,
and so the set cannot be multiple-free.
Alternative proof:
We will use a method of DESCENT.
We have a conjecture about whole numbers. If this is false,
there must be a smallest example contradicting this.
The Minimal Criminal...
Now construct from this a smaller such example.
But a smaller example cannot exist!
So we cannot find such an example at all,
And we have proved our conjecture.
It’s a powerful technique!
Conjecture: if we pick n + 1 of the numbers from 1 to 2n,
this set will never be multiple-free.
Call this statement Sn. Task: prove this for all n  1.
Suppose our conjecture is false.
Let n be the first number for which Sk fails,
so we can pick n + 1 numbers from the first 2n
so that our set is multiple-free,
and we cannot do this for any smaller k.
We are now going to attempt to show that
(if the above is true)
we must be able to find n - 1 numbers
from 1 to 2n - 2 that are multiple-free.
In which case, we have a contradiction!
There are 3 cases:
Case 3: delete one number from the set of n + 1
you have chosen – you now have a set of n numbers
from 1 to 2n - 2 which is multiple-free.
Case 2: delete either 2n or 2n - 1 from the set of n + 1
you have chosen – you now have a set of n numbers
from 1 to 2n - 2 which is multiple-free.
What about Case 1?
Case 1: neither n nor any factor of n can be in your set, because
2n is. So delete 2n and 2n - 1 from your list and add n. You now
have n numbers between 1 and 2n - 2 that are multiple-free.
So for Cases 1, 2, and 3, we have found a multiple-free set
for the numbers from 1 to 2n - 2.
But Sk was meant to be impossible
for any number less than n...
We thus have a contradiction, and so
choosing a multiple-free set
of size n + 1 from the numbers from 1 to 2n
must be impossible.
With thanks to:
Nrich, and Mazzafarius.
Carom is written by Jonny Griffiths, [email protected]