Question from Session 7: There are 1900 one-Swiss-franc coins lying on an enormous table. Some of them might touch each other, but they don't overlap. Show that you can always choose 475 of them such that no two chosen coins touch each other. Can you always choose 601 such coins?
Part I: Can we find 475 non-touching coins?
Yes, we can always find 475 coins that do not touch one another.
We model a graph G in which each one-Swiss-franc coin is a vertex and in which there exists an edge between each pair of coins that touch each other. As the coins are on a table (presumably flat) and do not overlap, we can assume that the graph G is planar. By the four-colour theorem, G can be coloured with four colours.
Let i be a colour such that i∈{1, 2, 3, 4} and let Gi be the subgraph of G containing the vertices coloured i. Then the average size of the subgraph of all the four colours is always:
We consider first the case that Gi=475 for all i∈{1,2,3,4}. Then we can find that all of the Gi are of size 475. This means that all four sets of 475 coins are found such that no coins in the same set touch each other. If there is a certain Gi greater than 475, we can always find a subset of Gi that contains 475 coins such that no coins in the subset touch each other.
We next consider the case that we find a certain Gi less than 475 for another i such that the average subgraph size is 475 and not below 475. It follows that we can find a set of 475 coins from this larger subgraph in which no two coins touch each other.
Part II: Can we find 601 non-touching coins?
We can find 601 coins that do not touch one another in the case where the coins are maximally packed.
It has been proven by Lagrange in 1773 that a lattice arrangement of circles with the highest density is the hexagonal packing arrangement. When the coins are maximally packed, the graph G becomes such that the internal facets of the graph can only be equilateral triangles.
There exists a uniform colouring in three colours (123) for a hexagonal packing arrangement. The 2-colourability of the graph G of the infinite hexagonal packing is provable by demonstrating 3-colourability on a unit cell of the hexagonal lattice and then tesselating the unit cell indefinitely:
Fig 1. 3-coloured unit cell in the infinite lattice
Then, following the line of thought in the first part, we let i be a colour such that i∈{1,2,3} and let Gi be the subgraph of G containing the vertices coloured i. Then the average size of the subgraph of all the four colours is always:
We can always find a certain Gi such that |Gi|>633 and none of the coins in Gi touch one another, and a subset of 601 non-touching coins can always be found in Gi.
□!
(24 Apr 2013, Dorigny in the Switz)
