Question from Session 3: Baron Münchhausen is very proud: "I chose a huge set of positive integers smaller than 2013, and yet among any four elements there are two such that one is divisible by the other." He went on boasting to his stupefied audience: "I bet no one could ever find such a set with more elements." However, the infamous storyteller was exaggerating again. The set he had found was rather small. Help him find a set that could save his honor.
Definition of the problem
We are tasked to construct the largest set of numbers such that
1. It is a subset of the set of natural numbers larger than or equal to 1 and less than or equal to 2013.
2. For any four numbers selected from from the set, there is at least one selected number which is divisible by another selected number.
If Baron Münchhausen makes a bet that no one can find a set larger than this set that we will constuct, it will not be possible for him to lose.
Solving the problem with paths
Let us rethink the set of all natural numbers from 1 to 2013 as a directional graph. Each number n is represented by a vertex vn. A vertex vn connects to another vertex vm only if m is divisible by n. For example, one such possible directional path in this graph would be:
v2→v4→v12→v36→v252→v2772
The path terminates at the vertex where it is not possible to multiply the number with any other number (picked from 2 to 2013) without producing a number larger than 2013. In the case above, 2772 * 2 = 5544 (> 2013).
For any two numbers picked from the path, the larger one is divisible by the smaller one. This is because we constructed the graph in a way that a vertex on a path is divisible by all its predecessors.
In order to satisfy the condition that for any four numbers chosen in the subset, one of it is divisible by another, we should construct a subset such that all the numbers can fit into three paths. In order to find the largest subset, we should construct the three unique paths that are as long as possible.
Finding the three longest possible unique paths
To find the longest path i.e. the path containing the most number of numbers below 2013, we have to let each successive number on the path be the smallest multiple of its predecessor. This would yield m=2n for every connection vn→vm. We use the smallest number of the set, 1, as the starting vertex for this path:
v1→v2→v4→v16→v22→⋯→v1024
As 1024 * 2 = 2048 > 2013, the graph terminates. 1024 being 210, this path has 10 + 1 = 11 vertices.
The second longest path uses 3 as the starting vertex, as the numbers 1 and 2 are already included in the first path. As in the last path, we make each successive number in the path to be two times its predecessor:
v3→v6→v12→v24→v48→⋯→v1536
As 1536 is 3 * 29, this path has 9 + 1 = 10 vertices.
The third path uses 5 as the starting vertex, as the multiples of 4 are already included in the previous two paths. Again we make each successive number in the path to be two times its predecessor:
v5→v10→v20→v40→v80→⋯→v1280
As 1280 is 5 * 28, this path has 8 + 1 = 9 vertices.
We thus obtain the set of 9 + 10 + 11 = 30 numbers from the above three paths
{1, 2, 3, 4, 5, 6, 10, 12, 16, 20, 24, 32, 40, 48, 64, 80, 96, 128, 160, 192, 256, 320, 384, 512, 640, 768, 1024, 1280, 1536}
For every 4 numbers that are chosen from this set, two will land on the same path.
If two numbers land on the same path, then one number out of the two is divisible by the other. This is just how we have constructed the paths in the first place. So for every four numbers chosen, at least one number is divisible by another in the set.
Also by our construction, this is the maximal set. If the baron had chosen this set instead of whatever he had chosen before, his challenger can never find any larger set of numbers to fulfill the same mentioned criterion.
□!
(13 Mar 2013, Dorigny in the Switz)
