Seven Smurfs live in seven mushroom houses. There is a tunnel between every pair of houses, so from any house you can walk to any other house. One of the Smurfs, Clumsy, starts walking from his house, but he must not use the same tunnel more than once. He keeps walking until he reaches a house where all the tunnels have already been used. Where will Clumsy’s journey end?
A battle of the captains was held at a maths battle. The task was to write the smallest number that is divisible by \(60\) and it’s digits are only ’\(1\)’s or ’\(0\)’s. What is the answer?
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:
A light pattern is just which lights are ON or OFF on the board.
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:
\(x_1+y_1\sqrt{d} < x_2+y_2\sqrt{d}\),
\(x_1<x_2\) and \(y_1<y_2\),
\(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.