As the semester is almost over, I have finally found an
interesting problem to share with you.
The question goes as follows:
Place 10 points
equidistant from each other along the circumference of a circle. Color 5 points
red and 5 points blue in such a way that it is not possible to find two
triangles, one with blue vertices and one with red vertices, that are identical
(they can perfectly overlap each other).
As it turns out, this is actually not possible – you can
always find two triangles, one with blue vertices and one with red vertices,
that will perfectly overlap each other.
The great thing about this problem is that it extends into other more interesting problems. For example, we could try varying the amount of points we take (like 12, or 20). We could also change the shape (instead of a triangles, we could pick a quadrilateral).
Let’s change the above problem to its most general case: Place
2N (N > 0) points equidistant from each other along the circumference of a
circle. Color N of the points blue and N of the points red. Can this be done in
a way such that no two K-sided identical polygons (one with red vertices and
one with blue) can be found?
The answer: if N is large enough, this is impossible (you
can always find two identical K-sided polygons).
Proof:
When I first started thinking about this problem, it seemed intuitive to try to prove it by contradiction. Here is one approach:
Let’s consider a circle with 2N equidistant points along its
circumference. We will assume that we have found a way to color N of the points
red and N of the points blue in such a way that there are no two K-sided
polygons (one red and one blue) that are identical. Let’s now imagine that
while the blue points remain in their position, the red points will start
moving clock-wise around the circle in equal steps. The steps are chosen in
such a way that the points will end up in their original position after 2N
steps (one step is equal to the distance between two points).
Obviously, as the red points move they will at times overlap the blue points. Upon the completion of the 2N steps, it is clear that each of the red point must have overlapped all of the N blue points one by one. How many of such overlaps happen? Well, exactly N2 since each of the red points overlaps each of the N blue points.
Now, at each step, there will be some red points overlapping blue points. This is not a fixed number as sometimes there could be more overlaps and sometimes there may be none.
However, if at a certain step at least K points overlap, it
means that we have actually found two K-sided polygons (one red and one blue)
that are identical. Since we have assumed that this cannot happen, this means
that at any step there cannot be more than K-1 overlaps. Since there are 2N
steps, this means that the number of overlaps should be less than or equal to
2N(k – 1). In fact, because at the last step the red points return to their
original position (i.e. no overlaps), the total number should be no greater
than (2N-1)(K-1)
Since we know that the actual number of overlaps is N2
this means:
N2 £ (2N-1)(K-1)
(1)
The above inequality does not stand if N is big enough. For
example if N = 2K then
N2 = 4K2 > (4K - 1)(K - 1) = 4K2
– 5K + 1
Note: 4K2 > 4K2 – 5K + 1 Þ 5K
> 1 (always true when K > 0 and since we are considering polygons, K will
never be 0)
This proves that given a big enough N, we are always going
to find two K-sides polygons that are equal no matter how the red and blue points
are chosen.
Now, going back to the original problem, for triangles we
have K = 3. This means (1) becomes:
N2 £ 2(2N-1)
(2)
Taking N = 2K = 6, we can see that N2 = 36
> 22 = 2(2N-1)
We can also see that for any N > 6 the inequality will
not stand (in fact any N > 3 will
work).
So, that’s the end of the solution. I hope you found this
problem interesting.
Good luck to everyone on their exams!
