Proof

If we split a set \(S\) of integers into two subsets \(A\) and \(B\) whose intersection is empty and whose union is the whole of \(S\), and such that

• the sum of the elements of \(A\) is equal to the sum of the elements of \(B\)
• and the sum of the squares of the elements of \(A\) is equal to the sum of the squares of the elements of \(B\),

1. Find a balanced partition of the set \(\{1, 2, 3, 4, 5, 6, 7, 8\}\) into two subsets \(A\) and \(B\), each of size 4.
2. Given that \(a_1, a_2, \ldots, a_m\) and \(b_1, b_2, \ldots, b_m\) are sequences with \[\sum_{k=1}^m a_k = \sum_{k=1}^m b_k \quad \text{and} \quad \sum_{k=1}^m a_k^2 = \sum_{k=1}^m b_k^2,\] show that \[\sum_{k=1}^m a_k^3 + \sum_{k=1}^m (c + b_k)^3 = \sum_{k=1}^m b_k^3 + \sum_{k=1}^m (c + a_k)^3\] for any real number \(c\).
3. Find, with justification, a balanced partition of the set \(\{1, 2, 3, \ldots, 16\}\) into two subsets \(A\) and \(B\), each of size 8, which also has the property that
   • the sum of the cubes of the elements of \(A\) is equal to the sum of the cubes of the elements of \(B\).
4. You are given that the sets \(A = \{1, 3, 4, 5, 9, 11\}\) and \(B = \{2, 6, 7, 8, 10\}\) form a balanced partition of the set \(\{1, 2, 3, \ldots, 11\}\). Let \(S = \{n^2, (n+1)^2, (n+2)^2, \ldots, (n+11)^2\}\), where \(n\) is any positive integer. Find, with justification, two subsets \(C\) and \(D\) of \(S\) whose intersection is empty and whose union is the whole of \(S\), and such that
   • the sum of the elements of \(C\) is equal to the sum of the elements of \(D\).

In the equality \[ 4 + 5 + 6 + 7 + 8 = 9 + 10 + 11, \] the sum of the five consecutive integers from 4 upwards is equal to the sum of the next three consecutive integers. Throughout this question, the variables \(n\), \(k\) and \(c\) represent positive integers.

1. Show that the sum of the \(n + k\) consecutive integers from \(c\) upwards is equal to the sum of the next \(n\) consecutive integers if and only if \[ 2n^2 + k = 2ck + k^2. \]
2. Find the set of possible values of \(n\), and the corresponding values of \(c\), in each of the cases
   1. \(k = 1\)
   2. \(k = 2\).
3. Show that there are no solutions for \(c\) and \(n\) if \(k = 4\).
4. Consider now the case where \(c = 1\).
   1. Find two possible values of \(k\) and the corresponding values of \(n\).
   2. Show, given a possible value \(N\) of \(n\), and the corresponding value \(K\) of \(k\), that \[ N' = 3N + 2K + 1 \] will also be a possible value of \(n\), with \[ K' = 4N + 3K + 1 \] as the corresponding value of \(k\).
   3. Find two further possible values of \(k\) and the corresponding values of \(n\).

1. Given that \(a\), \(b\) and \(c\) are the lengths of the sides of a triangle, explain why \(c < a + b\), \(a < b + c\) and \(b < a + c\).
2. Use a diagram to show that the converse of the result in part (i) also holds: if \(a\), \(b\) and \(c\) are positive numbers such that \(c < a + b\), \(a < b + c\) and \(b < c + a\) then it is possible to construct a triangle with sides of length \(a\), \(b\) and \(c\).
3. When \(a\), \(b\) and \(c\) are the lengths of the sides of a triangle, determine in each case whether the following sets of three lengths can
   • always
   • sometimes but not always
   • never
   form the sides of a triangle. Prove your claims. (A) \(a+1\), \(b+1\), \(c+1\). (B) \(\dfrac{a}{b}\), \(\dfrac{b}{c}\), \(\dfrac{c}{a}\). (C) \(|a-b|\), \(|b-c|\), \(|c-a|\). (D) \(a^2 + bc\), \(b^2 + ca\), \(c^2 + ab\).
4. Let \(\mathrm{f}\) be a function defined on the positive real numbers and such that, whenever \(x > y > 0\), \[\mathrm{f}(x) > \mathrm{f}(y) > 0 \quad \text{but} \quad \frac{\mathrm{f}(x)}{x} < \frac{\mathrm{f}(y)}{y}.\] Show that, whenever \(a\), \(b\) and \(c\) are the lengths of the sides of a triangle, then \(\mathrm{f}(a)\), \(\mathrm{f}(b)\) and \(\mathrm{f}(c)\) can also be the lengths of the sides of a triangle.

Consider the following steps in a proof that \(\sqrt{2} + \sqrt{3}\) is irrational.

1. If an integer \(a\) is not divisible by 3, then \(a = 3k \pm 1\), for some integer \(k\). In both cases, \(a^2\) is one more than a multiple of 3.
2. Suppose that \(\sqrt{2} + \sqrt{3}\) is rational, and equal to \(\frac{a}{b}\), where \(a\) and \(b\) are positive integers with no common factor greater than one.
3. Then \(a^4 + b^4 = 10a^2b^2\).
4. So if \(a\) is divisible by 3, then \(b\) is divisible by 3.
5. Hence \(\sqrt{2} + \sqrt{3}\) is irrational.

1. Show clearly that steps 1, 3 and 4 are all valid and that the conclusion 5 follows from the previous steps of the argument.
2. Prove, by means of a similar method but using divisibility by 5 instead of 3, that \(\sqrt{6} + \sqrt{7}\) is irrational. Why can divisibility by 3 not be used in this case?

The sequence \(u_0, u_1, \ldots\) is said to be a constant sequence if \(u_n = u_{n+1}\) for \(n = 0, 1, 2, \ldots\). The sequence is said to be a sequence of period 2 if \(u_n = u_{n+2}\) for \(n = 0, 1, 2, \ldots\) and the sequence is not constant.

1. A sequence of real numbers is defined by \(u_0 = a\) and \(u_{n+1} = f(u_n)\) for \(n = 0, 1, 2, \ldots\), where $$f(x) = p + (x - p)x,$$ and \(p\) is a given real number. Find the values of \(a\) for which the sequence is constant. Show that the sequence has period 2 for some value of \(a\) if and only if \(p > 3\) or \(p < -1\).
2. A sequence of real numbers is defined by \(u_0 = a\) and \(u_{n+1} = f(u_n)\) for \(n = 0, 1, 2, \ldots\), where $$f(x) = q + (x - p)x,$$ and \(p\) and \(q\) are given real numbers. Show that there is no value of \(a\) for which the sequence is constant if and only if \(f(x) > x\) for all \(x\). Deduce that, if there is no value of \(a\) for which the sequence is constant, then there is no value of \(a\) for which the sequence has period 2. Is it true that, if there is no value of \(a\) for which the sequence has period 2, then there is no value of \(a\) for which the sequence is constant?

1. Find all pairs of positive integers \((n,p)\), where \(p\) is a prime number, that satisfy \[ n!+ 5 =p \,. \]
2. In this part of the question you may use the following two theorems:
   1. For \(n\ge 7\), \(1! \times 3! \times \cdots \times (2n-1)! > (4n)!\,\).
   2. For every positive integer \(n\), there is a prime number between \(2n\) and \(4n\).
   Find all pairs of positive integers \((n,m)\) that satisfy \[ 1! \times 3! \times \cdots \times (2n-1)! = m! \,. \]

The sequence of numbers \(x_0\), \(x_1\), \(x_2\), \(\ldots\) satisfies \[ x_{n+1} = \frac{ax_n-1}{x_n+b} \,. \] (You may assume that \(a\), \(b\) and \(x_0\) are such that \(x_n+b\ne0\,\).) Find an expression for \(x_{n+2}\) in terms of \(a\), \(b\) and \(x_n\).

1. Show that \(a+b=0\) is a necessary condition for the sequence to be periodic with period 2. Note: The sequence is said to be periodic with period \(k\) if \(x_{n+k} = x_n\) for all \(n\), and there is no integer \(m\) with \(0 < m < k\) such that \(x_{n+m} = x_n\) for all \(n\).
2. Find necessary and sufficient conditions for the sequence to have period 4.

The set \(S\) consists of all the positive integers that leave a remainder of 1 upon division by 4. The set \(T\) consists of all the positive integers that leave a remainder of 3 upon division by 4.

1. Describe in words the sets \(S \cup T\) and \(S \cap T\).
2. Prove that the product of any two integers in \(S\) is also in \(S\). Determine whether the product of any two integers in \(T\) is also in \(T\).
3. Given an integer in \(T\) that is not a prime number, prove that at least one of its prime factors is in \(T\).
4. For any set \(X\) of positive integers, an integer in \(X\) (other than 1) is said to be \(X\)-prime if it cannot be expressed as the product of two or more integers all in \(X\) (and all different from 1).
   • \(\bf (a)\) Show that every integer in \(T\) is either \(T\)-prime or is the product of an odd number of \(T\)-prime integers.
   • \(\bf (b)\) Find an example of an integer in \(S\) that can be expressed as the product of \(S\)-prime integers in two distinct ways. [Note: \(s_1s_2\) and \(s_2s_1\) are not counted as distinct ways of expressing the product of \(s_1\) and \(s_2\).]

Show that:

1. \(1+2+3+ \cdots + n = \frac12 n(n+1)\);
2. if \(N\) is a positive integer, \(m\) is a non-negative integer and \(k\) is a positive odd integer, then \((N-m)^k +m^k\) is divisible by \(N\).

If \(s_1\), \(s_2\), \(s_3\), \(\ldots\) and \(t_1\), \(t_2\), \(t_3\), \(\ldots\) are sequences of positive numbers, we write \[ (s_n)\le (t_n) \] to mean

1. \((1000n) \le (n^2)\,\).
2. If it is not the case that \((s_n)\le (t_n)\), then it is the case that \((t_n)\le (s_n)\,\).
3. If \((s_n)\le (t_n)\) and \((t_n) \le (u_n)\), then \((s_n)\le (u_n)\,\).
4. \((n^2)\le (2^n)\,\).

1. In the following argument to show that \(\sqrt2\) is irrational, give proofs appropriate for steps 3, 5 and 6.
   1. Assume that \(\sqrt2\) is rational.
   2. Define the set \(S\) to be the set of positive integers with the following property:
      \(n\) is in \(S\) if and only if \(n \sqrt2\) is an integer.
   3. Show that the set \(S\) contains at least one positive integer.
   4. Define the integer \(k\) to be the smallest positive integer in \(S\).
   5. Show that \((\sqrt2-1)k\) is in \(S\).
   6. Show that steps 4 and 5 are contradictory and hence that \(\sqrt2\) is irrational.
2. Prove that \(2^{\frac13} \) is rational if and only if \(2^{\frac23}\) is rational. Use an argument similar to that of part (i) to prove that \(2^{\frac13}\) and \(2^{\frac23}\) are irrational.

An operator \(\rm D\) is defined, for any function \(\f\), by \[ {\rm D}\f(x) = x\frac{\d\f(x)}{\d x} .\] The notation \({\rm D}^n\) means that \(\rm D\) is applied \(n\) times; for example \[ \displaystyle {\rm D}^2\f(x) = x\frac{\d\ }{\d x}\left( x\frac{\d\f(x)}{\d x} \right) \,. \] Show that, for any constant \(a\), \({\rm D}^2 x^a = a^2 x^a\,\).

1. Show that if \(\P(x)\) is a polynomial of degree \(r\) (where \(r\ge1\)) then, for any positive integer \(n\), \({\rm D}^n\P(x)\) is also a polynomial of degree \(r\).
2. Show that if \(n\) and \(m\) are positive integers with \(n < m\), then \({\rm D}^n(1-x)^m\) is divisible by \((1-x)^{m-n}\).
3. Deduce that, if \(m\) and \(n\) are positive integers with \(n < m\), then \[ \sum_{r=0}^m (-1)^r \binom m r r^n =0 \, . \]
4. [Not on original paper] Let \(\f_n(x) = D^n(1-x)^n\,\), where \(n\) is a positive integer. Prove that \(\f_n(1)=(-1)^nn!\, \).

All numbers referred to in this question are non-negative integers.

1. Express each of the numbers 3, 5, 8, 12 and 16 as the difference of two non-zero squares.
2. Prove that any odd number can be written as the difference of two squares.
3. Prove that all numbers of the form \(4k\), where \(k\) is a non-negative integer, can be written as the difference of two squares.
4. Prove that no number of the form \(4k+2\), where \(k\) is a non-negative integer, can be written as the difference of two squares.
5. Prove that any number of the form \(pq\), where \(p\) and \(q\) are prime numbers greater than 2, can be written as the difference of two squares in exactly two distinct ways. Does this result hold if \(p\) is a prime greater than 2 and \(q=2\)?
6. Determine the number of distinct ways in which 675 can be written as the difference of two squares.

1. Let \(f(x) = (x+2a)^3 -27 a^2 x\), where \(a\ge 0\). By sketching \(f(x)\), show that \(f(x)\ge 0\) for \(x \ge0\).
2. Use part (i) to find the greatest value of \(xy^2\) in the region of the \(x\)-\(y\) plane given by \(x\ge0\), \(y\ge0\) and \(x+2y\le 3\,\). For what values of \(x\) and \(y\) is this greatest value achieved?
3. Use part (i) to show that \((p+q+r)^3 \ge 27pqr\) for any non-negative numbers \(p\), \(q\) and \(r\). If \((p+q+r)^3 = 27pqr\), what relationship must \(p\), \(q\) and \(r\) satisfy?

1. Write down a solution of the equation \[ x^2-2y^2 =1\,, \tag{\(*\)} \] for which \(x\) and \(y\) are non-negative integers. Show that, if \(x=p\), \(y=q\) is a solution of (\(*\)), then so also is \(x=3p+4q\), \(y=2p+3q\). Hence find two solutions of \((*)\) for which \(x\) is a positive odd integer and \(y\) is a positive even integer.
2. Show that, if \(x\) is an odd integer and \(y\) is an even integer, \((*)\) can be written in the form \[ n^2 = \tfrac12 m(m+1)\,, \] where \(m\) and \(n\) are integers.
3. The positive integers \(a\), \(b\) and \(c\) satisfy \[ b^3=c^4-a^2\,, \] where \(b\) is a prime number. Express \(a\) and \(c^2\) in terms of \(b\) in the two cases that arise. Find a solution of \(a^2+b^3=c^4\), where \(a\), \(b\) and \(c\) are positive integers but \(b\) is not prime.

In this question, you may assume that, if \(a\), \(b\) and \(c\) are positive integers such that \(a\) and \(b\) are coprime and \(a\) divides \(bc\), then \(a\) divides \(c\). (Two positive integers are said to be coprime if their highest common factor is 1.)

1. Suppose that there are positive integers \(p\), \(q\), \(n\) and \(N\) such that \(p\) and \(q\) are coprime and \(q^nN=p^n\). Show that \(N=kp^n\) for some positive integer \(k\) and deduce the value of \(q\). Hence prove that, for any positive integers \(n\) and \(N\), \(\sqrt[n]N\) is either a positive integer or irrational.
2. Suppose that there are positive integers \(a\), \(b\), \(c\) and \(d\) such that \(a\) and \(b\) are coprime and \(c\) and \(d\) are coprime, and \(a^ad^b = b^a c^b \,\). Prove that \(d^b = b^a\) and deduce that, if \(p\) is a prime factor of \(d\), then \(p\) is also a prime factor of \(b\). If \(p^m\) and \(p^n\) are the highest powers of the prime number \(p\) that divide \(d\) and \(b\), respectively, express \(b\) in terms of \(a\), \(m\) and \(n\) and hence show that \(p^n\le n\). Deduce the value of \(b\). (You may assume that if \(x > 0\) and \(y\ge2\) then \(y^x > x\).) Hence prove that, if \(r\) is a positive rational number such that \(r^r\) is rational, then \(r\) is a positive integer.

1. The numbers \(m\) and \(n\) satisfy \[ m^3=n^3+n^2+1\,. \tag{\(*\)} \]
   • Show that \(m > n\). Show also that \(m < n+1\) if and only if \(2n^2+3n > 0\,\). Deduce that \(n < m < n+1\) unless \(-\frac32 \le n \le 0\,\).
   • Hence show that the only solutions of \((*)\) for which both \(m\) and \(n\) are integers are \((m,n) = (1,0)\) and \((m,n)= (1,-1)\).
2. Find all integer solutions of the equation \[ p^3=q^3+2q^2-1\,. \]

Write down the cubes of the integers \(1, 2, \ldots , 10\). The positive integers \(x\), \(y\) and \(z\), where \(x < y\), satisfy \[ x^3+y^3 = kz^3\,, \tag{\(*\)} \] where \(k\) is a given positive integer.

1. In the case \(x+y =k\), show that \[ z^3 = k^2 -3kx+3x^2\,. \] Deduce that \((4z^3 - k^2)/3\) is a perfect square and that \(\frac14 {k^2} \le z^3 < k^2\,\). Use these results to find a solution of \((*)\) when \(k=20\).
2. By considering the case \(x+y = z^2\), find two solutions of \((*)\) when \(k=19\).

1. Suppose that \(a\), \(b\) and \(c\) are integers that satisfy the equation \[ a^{3}+3b^{3}=9c^{3}. \] Explain why \(a\) must be divisible by 3, and show further that both \(b\) and \(c\) must also be divisible by 3. Hence show that the only integer solution is \(a=b=c=0\,\).
2. Suppose that \(p\), \(q\) and \(r\) are integers that satisfy the equation \[ p^4 +2q^4 = 5r^4 \,.\] By considering the possible final digit of each term, or otherwise, show that \(p\) and \(q\) are divisible by 5. Hence show that the only integer solution is \(p=q=r=0\,\).

The vertices \(A\), \(B\), \(C\) and \(D\) of a square have coordinates \((0,0)\), \((a,0)\), \((a,a)\) and \((0,a)\), respectively. The points \(P\) and \(Q\) have coordinates \((an,0)\) and \((0,am)\) respectively, where \(0 < m < n < 1\). The line \(CP\) produced meets \(DA\) produced at \(R\) and the line \(CQ\) produced meets \(BA\) produced at \(S\). The line \(PQ\) produced meets the line \(RS\) produced at \(T\). Show that \(TA\) is perpendicular to \(AC\). Explain how, given a square of area \(a^2\), a square of area \(2a^2\) may be constructed using only a straight-edge. [Note: a straight-edge is a ruler with no markings on it; no measurements (and no use of compasses) are allowed in the construction.]

Show Solution

+ - ↺

Note that \(CP\) has equation \(\frac{y-0}{x-an} = \frac{a-0}{a-an} = \frac{1}{1-n} \Rightarrow y = \frac{x-an}{1-n}\) Therefore \(R = (0, -\frac{an}{1-n})\) Note that \(CQ\) has equation \(\frac{y-am}{x} = \frac{a-am}{a} = 1-m \Rightarrow y = (1-m)x + am\) Therefore \(S = (-\frac{am}{1-m}, 0)\) \(PQ\) has equation \(\frac{y}{x-an} = \frac{am-0}{0-an} \Rightarrow y = -\frac{m}{n}x +am\) \(SR\) has equation \(\frac{y}{x+\frac{am}{1-m}} = \frac{-\frac{an}{1-n}}{\frac{am}{1-m}} = -\frac{n(1-m)}{m(1-n)} \Rightarrow y =-\frac{n(1-m)}{m(1-n)} x -a\frac{n}{1-n}\) So \(PQ \cap SR\) has \begin{align*} && -\frac{m}{n}x +am &= -\frac{n(1-m)}{m(1-n)} x -a\frac{n}{1-n} \\ && x \left (\frac{n(1-m)}{m(1-n)} - \frac{m}{n} \right) &= -am - \frac{an}{1-n} \\ \Rightarrow && x \left ( \frac{n^2(1-m)-m^2(1-n)}{nm(1-n)} \right) &= -\frac{a(m(1-n)+n)}{1-n} \\ \Rightarrow && x \left ( \frac{(m-n)(mn-n-m)}{mn(1-n)} \right) &= \frac{a(mn-m-n)}{1-n} \\ \Rightarrow && x &= \frac{amn}{m-n} \\ && y &= -\frac{amn}{m-n} \end{align*} Therefore clearly \(TA\) is perpendicular to \(AC\) since they are the lines \(y = -x\) and \(y = x\) Given this method we can construct the perpendicular to the diagonal through the vertex. Doing this at \(A\) we can construct \(C'\) the reflection of \(C\) in \(AB\). We can do the same to find the reflection of \(A\) and so we have a square with sidelengths \(\sqrt{2}a\) and hence area \(2a^2\)

+ - ↺

A {\em proper factor} of an integer \(N\) is a positive integer, not \(1\) or \(N\), that divides \(N\).

1. Show that \(3^2\times 5^3\) has exactly \(10\) proper factors. Determine how many other integers of the form \(3^m\times5^n\) (where \(m\) and \(n\) are integers) have exactly 10 proper factors.
2. Let \(N\) be the smallest positive integer that has exactly \(426\) proper factors. Determine \(N\), giving your answer in terms of its prime factors.

What does it mean to say that a number \(x\) is irrational? Prove by contradiction statements A and B below, where \(p\) and \(q\) are real numbers.

• A: If \(pq\) is irrational, then at least one of \(p\) and \(q\) is irrational.
• B: If \(p+q\) is irrational, then at least one of \(p\) and \(q\) is irrational.

• C: If \(p\) and \(q\) are irrational, then \(p+q\) is irrational.

Prove that, if \(c\ge a\) and \(d\ge b\), then \[ ab+cd\ge bc+ad\,. \tag{\(*\)} \]

1. If \(x\ge y\), use \((*)\) to show that \(x^2+y^2\ge 2xy\,\). If, further, \(x\ge z\) and \(y\ge z\), use \((*)\) to show that \(z^2+xy\ge xz+yz\) and deduce that \(x^2+y^2+z^2\ge xy+yz+zx\,\). Prove that the inequality \(x^2+y^2+z^2\ge xy+yz+zx\,\) holds for all \(x\), \(y\) and \(z\).
2. Show similarly that the inequality \[\frac st +\frac tr +\frac rs +\frac ts +\frac rt +\frac sr \ge 6\] holds for all positive \(r\), \(s\) and \(t\).

The polynomial \(\p(x)\) is given by \[ \ds \p(x)= x^n +\sum\limits_{r=0}^{n-1}a_rx^r\,, \] where \(a_0\), \(a_1\), \(\ldots\) , \(a_{n-1}\) are fixed real numbers and \(n\ge1\). Let \(M\) be the greatest value of \(\big\vert \p(x) \big\vert\) for $\vert x \vert\le 1\(. Then Chebyshev's theorem states that \)M\ge 2^{1-n}$.

1. Prove Chebyshev's theorem in the case \(n=1\) and verify that Chebyshev's theorem holds in the following cases:
   1. \( \p(x) = x^2 - \frac12\,\);
   2. \(\p(x) = x^3 - x \,\).
2. Use Chebyshev's theorem to show that the curve $ \ y= 64x^5+25x^4-66x^3-24x^2+3x+1 \ $ has at least one turning point in the interval \(-1\le x \le 1\).

A sequence of points \((x_1,y_1)\), \((x_2,y_2)\), \(\ldots\) in the cartesian plane is generated by first choosing \((x_1,y_1)\) then applying the rule, for \(n=1\), \(2\), \(\ldots\), \[ (x_{n+1}, y_{n+1}) = (x_n^2-y_n^2 +a, \; 2x_ny_n+b+2)\,, \] where \(a\) and \(b\) are given real constants.

1. In the case \(a=1\) and \(b=-1\), find the values of \((x_1,y_1)\) for which the sequence is constant.
2. Given that \((x_1,y_1) = (-1,1)\), find the values of \(a\) and \(b\) for which the sequence has period 2.