Pigeons and coatings

The three "pigeon" problems posed last week , despite their relative simplicity, provoked numerous and interesting comments.

The first is the simplest: if we throw a die 12 times, it could happen, although it is unlikely (how unlikely?), that each of the six numbers would come up twice, so we would have to throw it 13 times to be absolutely certain that some number will come up at least three times.

The second can be approached in different ways. Here's how Luis Ortiz did it:

"The 12-digit problem is clearly illustrated using a table. We arrange the 100 possible two-digit numbers in rows of 11 consecutive numbers each, starting at 00, as follows:

00 01 02 03 04 05 06 07 08 09 10

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

· · ·

88 89 90 91 92 93 94 95 96 97 98

99

In this table, the difference between any two numbers in the same column is a multiple of 11, or in other words, both digits are equal. If we choose any 12 numbers in the table, at least two of them must be in the same column, meaning their difference will have both digits equal. Indeed: ultimately, it's a pigeon loft with 11 boxes and 12 pigeons.

I said at the end of the previous post that the pigeonhole principle allows us to effectively address some problems by combining it with graph theory, and the solution provided by Manuel Amorós for the third of last week's problems is a good example of this:

“The friendship problem is clearly seen in a colored graph where the points are people and the edges express the relationships: a blue edge if they know each other and a red one otherwise. The aim is to demonstrate the existence of a monochrome graph. From any vertex P, 5 edges emanate, blue or red. Necessarily, there will be 3 of the same color, let's say blue. The 3 corresponding vertices will in turn be connected to each other , and there can be two cases: either all 3 edges of said triangle are red (we would have a monochrome triangle), or there is one blue edge. This edge, together with the 2 that emanate from its ends towards P, form a blue triangle.”

Coatings with similar figures

Without leaving our conceptual pigeon loft (although the relationship may not be obvious), Salva Fuster proposed the following covering problem:

“Given an equilateral triangle, how many smaller equilateral triangles are required, at a minimum, to cover it?”

These smaller triangles do not have to be equal and can overlap (otherwise the answer would obviously be 4).

The problem admits interesting variations and generalizations : Given a square, how many smaller squares are required, at a minimum, to cover it? Can the criterion be generalized to other regular polygons? And to irregular polygons? And to the circle?

And finally, another problem (subtly related to the SF one) in which the equilateral triangle and the pigeonhole principle converge:

Given any 5 points in an equilateral triangle with sides of 1 meter, can they be more than 50 cm apart?