Problems

Welcome back from the summer holidays! We hope you’re rested and ready for an exciting year of problems. Today we’re going to dive right into our first topic with a fun game called “Lights Out."

Imagine a grid of square buttons. Each square has a light that can be ON or OFF. When you press a square, that light flips, and so do the lights directly above, below, left, and right. In today’s pictures, dark blue means ON and light blue means OFF. If you want to try it at home, search “Lights Out (game)” on Wikipedia for an interactive version. It may be useful for some of the harder problems.

Before we start, let’s quickly define two key words:

1. A light pattern is just which lights are ON or OFF on the board.

2. A plan is the set of buttons you choose to press to make a pattern. In Examples 1 and  2 we’ll see why a plan only needs to say which buttons are pressed: the order doesn’t matter, and each button is pressed either once or not at all.

Suppose that \(x_1+y_1\sqrt{d}\) and \(x_2+y_2\sqrt{d}\) give solutions to Pell’s equation \(x^2-dy^2=1\) and \(x_1,x_2,y_1,y_2\geq 0\). Show that the following are equivalent:

1. \(x_1+y_1\sqrt{d} < x_2+y_2\sqrt{d}\),

2. \(x_1<x_2\) and \(y_1<y_2\),

3. \(x_1<x_2\) or \(y_1<y_2\).

If Pell’s equation \(x^2-dy^2 = 1\) has a nontrivial solution \((x_1,y_1)\), show that it has infinitely many distinct solutions.

Show that there are infinitely many triples of consecutive integers, each of which is a sum of the square of two integers.

Suppose that Pell’s equation \(x^2-dy^2=1\) has a solution \((x_1,y_1)\) where \(x_1,y_1\) are positive and \(y_1\) is minimal among all solutions with positive \(x,y\). Show that if \(x+y\sqrt{d}\) gives a solution to \(x^2-dy^2=1\), then \(x+y\sqrt{d}=\pm(x_1+y_1\sqrt{d})^k\) for some integer \(k\).

Suppose that \(x_1+y_1\sqrt{d}\) gives a solution to Pell’s equation \(x^2-dy^2=1\). Define a sequence \(x_n+y_n\sqrt{d} = (x_1+y_1\sqrt{d})^n\). Show that we have the recurrence relations \(x_{n+2} = 2x_1x_{n+1}-x_n\) and \(y_{n+2} = 2x_1y_{n+1}-y_n\).

Prove that the only solution to \(5^a-3^b=2\) with \(a,b\) being positive integers is \(a=b=1\).

Show that Pell’s equation \(x^2-dy^2=1\) has a nontrivial solution.

For the following equations, find the integer solution \((x,y)\) with the smallest possible absolute value of \(y\).

• \(x^2 - 7y^2 = 1\);

• \(x^2 - 7y^2 = 29\).

Find the integer solution \((x,y)\) with the smallest possible absolute value of \(y\). \(x^2 - 2y^2 = 1\);

This equation helps to find all the square-triangular numbers, namely all the numbers that are perfect squares and can be represented as the sum \(1+2+3+...m\) for some \(m\). Finding such a number is equivalent to finding a solution to the equation: \(2n^2 = m(m+1)\). Or finding a solution to the Pell’s equation \(x^2-2y^2 = 1\) for \(x=2m+1\), \(y=2n\).