Tag Archives: olympiad

May18

Rooms and reflections

Posted on by
Standard

Consider the following entry from my notebook (16-Feb-2014):

The Art Gallery Problem: An art gallery has the shape of a simple n-gon. Find the minimum number of watchmen needed to survey the building, no matter how complicated its shape. [Source: problem 25, chapter 2, Problem Solving Strategies, Arthur Engel]

Hint: Use triangulation and colouring. Not an easy problem, and in fact there is a book dedicated to the theme of this problem: Art Gallery Theorems and Algorithms by Joseph O’Rourke (see chapter one for detailed solution). No reflection involved.

Then we have a bit harder problem when we allow reflection (28-Feb-2017, Numberphile – Prof. Howard Masur):

The Illumination Problem: Can any room (need not be a polygon) with mirrored walls be always illuminated by a single point light source, allowing for the repeated reflection of light off the mirrored walls?

The answer is NO. Next obvious question is “What kind of dark regions are possible?”. This question has been answered for rational polygons.

This reminds me of the much simpler theorem from my notebook (13-Jan-2014):

The Carpets Theorem: Suppose that the floor of a room is completely covered by a collection of non-overlapping carpets. If we move one of the carpets, then the overlapping area is equal to the uncovered area of the floor. [Source: §2.6, Mathematical Olympiad Treasures, Titu Andreescu & Bogdan Enescu]

Why I mentioned this theorem? The animation of Numberphile video reminded me of carpets covering the floor.

And following is the problem which motivated me write this blog post (17-May-2018, PBS Infinite Series – Tai-Danae):

Secure Polygon Problem: Consider a n-gon with mirrored walls, with two points: a source point S and a target point T. If it is possible to place a third point B in the polygon such that any ray from the source S passes through this point B before hitting the target T, then the polygon is said to be secure. Is square a secure polygon?

The answer is YES.  Moreover, the solution is amazing. Reminding me of the cross diagonal cover problem.

Feb3

A sequence I didn’t like

Posted on by
Standard

Following is a problem I encountered many times in my high school olympiads, but was never able to solve it. Hence didn’t like it.

What is the 100th term in the sequence 1,2,2,3,3,3,4,4,4,4,5,\ldots?

Following is a quick solution:

In this post, I will discuss the solution given in The Green Book of Mathematical Problems (problem 14).

Determine a function f(n) such that the n^{th} term of the sequence 1,2,2,3,3,3,4,4,4,4,5,\ldots is given by \lfloor f(n)\rfloor.

Let’s denote the n^{th} number of the sequence by a_n, i.e. a_n=\lfloor f(n)\rfloor. The integer m first occurs in the sequence when each of the integers from 1 to m-1 have already appeared 1 to m-1 times, respectively. Hence, if a_n=m then
n = [1 + 2 + 3 + \ldots + (m-1)]+1 +\ell = \frac{m(m-1)}{2} + 1 + \ell
for \ell = 0,1,2,\ldots, m-1.

Hence we have:
\displaystyle{0\leq n - \frac{m(m-1)}{2} - 1 \leq m-1}

\displaystyle{\Rightarrow \frac{m^2-m+2}{2}\leq n \leq \frac{m^2+m}{2}}

\displaystyle{\Rightarrow m^2-m+2\leq 2n \leq m^2+m}

\displaystyle{\Rightarrow \left(m-\frac{1}{2}\right)^2+\frac{7}{4}\leq 2n \leq \left(m+\frac{1}{2}\right)^2-\frac{1}{4}}

\displaystyle{\Rightarrow (2m-1)^2+7\leq 8n \leq (2m+1)^2 - 1}

\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 \leq (2m+1)^2 - 8}

\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 < (2m+1)^2}

\displaystyle{\Rightarrow 2m-1 \leq \sqrt{8n-7}<2m+1}

\displaystyle{\Rightarrow m \leq \frac{1+\sqrt{8n-7}}{2} < m+1}

\displaystyle{\Rightarrow m=\left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor}

Hence we have a_n = \left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor. Thus, we have

\displaystyle{\boxed{f(n) =\frac{1+\sqrt{8n-7}}{2}}}

Now compared to the earlier solution obtained by observing the pattern, one might ask “Is there is a better formula?”. For that, you might also look at the discussion at Math.SE.

Oct14

Arithmetic & Geometry

Posted on by
Standard

After a month of the unexpected break from mathematics, I will resume the regular weekly blog posts. It’s a kind of relaunch of this blog, and I  will begin with the discussion of an arithmetic problem with a geometric solution.  This is problem 103 from  The USSR Olympiad Problem Book:

Prove that
\displaystyle{t_1+t_2+\ldots + t_n = \left\lfloor\frac{n}{1}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor + \ldots + \left\lfloor\frac{n}{n}\right\rfloor}
where t_k is the number of divisors of the natural number k.

One can solve this problem by using the principle of mathematical induction or using the fact that the number of integers of the sequence 1,2,3,\ldots , n which are divisible by any chosen integer k is equal to \left\lfloor \frac{n}{k}\right\rfloor. The second approach of counting suggests an elegant geometric solution.

Consider the equilateral hyperbola \displaystyle{y = \frac{k}{x}} , (of which we shall take only the branches in the first quadrant):
ss
We note all the points in the first quadrant which have integer coordinates as the intersection point of the dotted lines. Now, if an integer x is a divisor of the integer k, then the point (x,y) is a point on the graph of the hyperbola xy=k. Conversely, if the hyperbola xy=k contains an integer point, then the x-coordinate is a divisor of k. Hence the number of integers t_k is  equal to the number of the integer points lying on the hyperbola xy=k. The number t_k is thus equal to the number of absciassas of integer points lying on the hyperbola xy=k. Now, we make use of the fact that the hyperbola xy=n lies “farther out” in the quadrant than do xy=1, xy=2, xy=3, \ldots, xy=n-1. The following implication hold:

The sum t_1+t_2\ldots + t_n is equal to the number of integer points lying under or on the hyperbola xy=n. Each such point will lie on a hyperbola xy=k, where k\leq n. The number of integer points with abscissa k located under the hyperbola is equal to the integer part of the length of the segment \overline{AB} [in figure above k=3]. That is \left\lfloor\frac{n}{k}\right\rfloor, since \displaystyle{|\overline{AB}|=\frac{n}{k}}, i.e. ordinate of point A on hyperbola xy=n for abscissa k. Thus, we obtain

\displaystyle{t_1+t_2+\ldots + t_n = \left\lfloor\frac{n}{1}\right\rfloor + \left\lfloor\frac{n}{2}\right\rfloor + \left\lfloor\frac{n}{3}\right\rfloor + \ldots + \left\lfloor\frac{n}{n}\right\rfloor}

Caution: Excess of anything is harmful, even mathematics. 

Jun25

Finite Sum & Divisibility

Posted on by
Standard

I wish to discuss a small problem from The USSR Olympiad Problem Book (problem 59) about the finite sum of harmonic series. The problem asks us to prove that

\displaystyle{\sum_{k=2}^{n} \frac{1}{k}}  can never be an  integer for any value of n.

I myself couldn’t think much about how to prove such a statement. So by reading the solution, I realised that how a simple observation about parity leads to this conclusion.

Firstly, observe that among the natural numbers from 2 to n there is exactly one natural number which has the highest power of 2 as its divisor. Now, while summing up the reciprocals of these natural numbers we will get a fraction as the answer. In that fraction, the denominator will be an even number since it’s the least common multiple of all numbers from 2 to n. And the numerator will be an odd number since it’s the sum of (n-2) even numbers with one odd number (corresponding to the reciprocal of the number with the highest power of 2 as the factor). Since under no circumstances an even number can completely divide an odd number, denominator can’t be a factor of the numerator. Hence the fraction can’t be reduced to an integer and the sum can never be an integer.