12th Eötvös Competition Problems 1905

1. For what positive integers m, n can we find positive integers a, b, c such that a + mb = n and a + b = m^c. Show that there is at most one such solution for each m, n.

2. Divide the unit square into 9 equal squares (forming a 3 x 3 array) and color the central square red. Now subdivide each of the 8 uncolored squares into 9 equal squares and color each central square red. Repeat n times, so that the side length of the smallest squares is 1/3ⁿ. How many squares are uncolored? What is the total red area as n → ∞?

3. ABC is a triangle and R any point on the segment AB. Let P be the intersection of the line BC and the line through A parallel to CR. Let Q be the intersection of the line AC and the line through B parallel to CR. Show that 1/AP + 1/BQ = 1/CR.

Solutions

Problem 1

For what positive integers m, n can we find positive integers a, b, c such that a + mb = n and a + b = m^c. Show that there is at most one such solution for each m, n.

Solution

We fix c and solve for a and b.

We have n = a + mb = a + m(m^c - a)= m^c+1 - a(m-1). Hence (n-1)/(m-1) = (m^c+1-1)/(m-1) - a. So a = (m^c+1-1)/(m-1) - (n-1)/(m-1). Note that (m^c+1-1)/(m-1) is an integer, so a is an integer iff n-1 is a multiple of m-1. Also a is positive iff m^c+1 > n.

b = m^c - a = (n-1)/(m-1) - (m^c-1)/(m-1). So b is also an integer iff n-1 is a multiple of m-1, and is positive iff n > m^c.

If n is a power of m, then we cannot find an integer c such that m^c+1 > n > m^c, so there are no solutions. Otherwise, there is a unique c such that m^c+1 > n > m^c.

Thus we can find positive integers a, b, c iff m > 1, n-1 is a multiple of m-1, n is not a power of m and the solution is then unique.

Problem 2

Divide the unit square into 9 equal squares (forming a 3 x 3 array) and color the central square red. Now subdivide each of the 8 uncolored squares into 9 equal squares and color each central square red. Repeat n times, so that the side length of the smallest squares is 1/3ⁿ. How many squares are uncolored? What is the total red area as n → ∞?

Solution

8ⁿ uncolored squares after n steps. Total uncolored area = (8/9)ⁿ, so total red area = 1 - (8/9)ⁿ → 1 as n → ∞.

Problem 3

ABC is a triangle and R any point on the segment AB. Let P be the intersection of the line BC and the line through A parallel to CR. Let Q be the intersection of the line AC and the line through B parallel to CR. Show that 1/AP + 1/BQ = 1/CR.

Solution