Problems

Show that if a polynomial \(P(x)\) has an integer root (i.e: a root that is a whole number), then it can’t be that \(P(0)\) and \(P(1)\) are both odd.

Solve the equation \[\left(x^2-3x+3\right)^2-3\left(x^2-3x+3\right)+3=x\]

(USO 1974) Let \(a,b,c\) be three distinct integers, and let \(P(x)\) be a polynomial whose coefficients are all integers. Prove that it is not possible that the following three conditions hold at the same time: \(P(a)=b, P(b)=c,\) and \(P(c)=a\).

For a polynomial \(P(x)=ax^2+bx+c\), consider the following two kinds of transformations:

1. Swap coefficients \(a\) and \(c\). Hence the polynomial \(P(x)\) becomes \(cx^2+bx+a\) after this transformation.

2. For any number \(t\) of your choice, change the variable \(x\) into \(x+t\). For example, with the choice of \(t=1\), after this transformation, the polynomial \(x^2+x+1\) becomes \((x+1)^2+(x+1)+1=x^2+3x+3\).

Is it possible, using only a sequence of these two transformations, to change the polynomial \(x^2-x-2\) into the polynomial \(x^2-x-1\)?

Let \(x,x',y,y'\) be integers such that \(x+\sqrt{d}y=x'+\sqrt{d}y'\), where \(d\) is a number that is not a square. Show that \(x=x'\) and \(y=y'\).

Show that if \(u_1\) and \(u_2\) are solutions to Pell’s equation, then \(u_1u_2\) is also a solution to Pell’s equation. What can you conclude about the number of solutions, if there are any?

Find all integer solutions to \(x^2+y^2-1=4xy\).

In a bag we have \(99\) red balls and \(99\) blue balls. We take balls from the bag, two balls at a time:

• If the two balls are of the same colour, then we put in a red ball to the bag.

• If the two balls are of different colour, we return a blue ball to the bag.

Regardless, after each step, one ball is lost from the bag, so eventually there will be only one ball. What is the colour of this last ball?

Today we will learn a really useful strategy for solving a certain kind of problems. This strategy is called the invariance principle, and after working through this sheet you’ll be able to recognise easily when we need to use an invariant to solve a problem. This strategy is applicable to kinds of problems where some task is repeatedly performed, and we wish to see if it is possible to transform our “initial state" into some given “final state". The key is to ask yourself:

You have an \(8\times 8\) chessboard coloured in the usual way. You can pick any \(2\times 1\) or \(1\times 2\) piece and flip the white tiles to black tiles and vice-versa. Is it possible to finish with \(63\) white pieces and \(1\) black piece?