Monthly Archives: January 2024

Finitely many solutions

Posted on by
1

This post is aimed at secondary-school students pitched roughly at the level of the British Mathematical Olympiad. It is ostensibly about a certain class of number theory problems, but the main underlying mathematical principle is broader than this. The post is based on an in-person session I have given to students and at teachers’ conferences a few times over the past five years, but I’ve chosen to write it up at this moment because of the connection to Problem 4 on the most recent BMO1 paper, which we discuss later in the post.

Prologue

Alice and Bob make the following statements:

  • Alice: all prime numbers are odd.
  • Bob: we can’t say anything about whether prime numbers are odd or even.

These are different types of statement, one objective, one more subjective; but both are wrong. Alice is wrong because 2 is a prime, and 2 is of course even. Bob is wrong because while Alice is wrong, and the alternative statement “all prime numbers are even” is even more wrong1, there are plenty of possible statements that are true and useful, including

  • Cleo: all prime numbers are odd except 2.

and weaker versions (that may be more relevant in other contexts) like “all primes greater than 10^{2024} are odd”.

The characters now turn their attention to another family of integers, the square numbers \{1,4,9,16,25\ldots\}, and the sixth powers \{1,64, 729, 4096, 15625,\ldots\}

  • Alice: no square numbers are prime.
  • Bob: I agree.
  • Alice: most square numbers are not sixth powers.
  • Bob: hang on, but infinitely many square numbers are sixth powers?

The difficulty in the second statement is what does most mean in this context? The square of an integer n is a sixth power if and only if n is a cube, and so Alice’s statement is equivalent to the statement “most positive integers are not cubes”, which is intuitively reasonable, but would require more clarification than the analogous statement “most primes are odd”. Is it not relevant, for example, that 1/4 of the first eight positive integers are in fact cubes?

It is not impossible to formalise this notion of most in a reasonable way to permit the two statements above2.

But the bulk of this post will discuss situations that extend the first of these conversations, ie when it’s not true to say “all element of X have property Y”, but where it’s nonetheless possible to make a useful intermediate statement.

Warmup problems

I hope most readers know how to solve an equation such as

3x+4 = 2(x+7),

and indeed learning how to solve such equations forms a important milestone in mathematical education as the first example of various principles of algebra. When such equations are still novel, teachers would be advised to avoid examples such as

2x+4 = 2(x+7)\quad\text{or}\quad 2x+14 = 2(x+7),

for which the answers are, respectively, ‘no solutions’ and ‘every x satisfies this’. While they are perfectly valid equations, it means something slightly different to solve them, since the answer set has different structure and, more importantly, the method is different since it doesn’t consist of a sequence of a manipulations leading directly to the required conclusion x= \texttt{answer}.

However, I mention this in passing to clarify that even in the simplest possible family of equations (probably encountered somewhere between ages 9 and 13) we are mindful that not all equations have unique solutions.

I’ve adapted a problem from the American competition AIME:

Find all integers n\ge 1 such that \frac{(n+2)!-(n+1)!}{n!} is a prime.

One could start by writing \frac{(n+2)!-(n+1)!}{n!}=p if you wish, but in fact we only need to work with the left hand side, so it’s better to avoid this if possible. The key to this problem is to avoid the prime condition initially, and just manipulate the LHS until it simplifies as

\frac{(n+2)!-(n+1)!}{n!} = (n+1)(n+2)-(n+1)=(n+1)^2, (*)

which is never a prime, since (n+1)^2 is a square number and so, as already discussed, never a prime.

So at a meta-level, comparing with the other problem in this section, this one also begins with reversible algebraic manipulations, but does not end with a direct reduction to n = [...], and indeed the final step is not reversible at all.

Finally, we remark that the original version of the AIME problem was

Prove that for all integers n\ge 9, \frac{(n+2)!-(n+1)!}{n!} is a perfect square.

The same algebraic reduction as (*) resolves the original version without an extra step concerning primes.

To be, or not to be, a perfect square

The rest of this article will focus entirely on problems of the form: find all positive integers n such that […] is a perfect square.

As setup, we’ll always consider a function f(n), and the sequence f(1),f(2),f(3),… and the question, comment on the set of n is f(n) a square? In particular, this is a more open-ended question than for which n is f(n) a square, which requires a more exact answer. We’ll aim for one of the following possible answers:

  • f(n) is always a square;
  • f(n) is a square for infinitely many n;
  • f(n) is a square for only finitely many n;
  • f(n) is never a square.

Clearly this is not an exhaustive list of possible descriptions3 of the set under discussion, but it will do for now. The difference between the second and the third bullet point can be thought of as: “are there arbitrarily large values of n for which f(n) is a square?”

As some examples:

  • \frac{(n+2)!-(n+1)!}{n!} is always a square, because (n+1)^2 is always a square.
  • (n+2)^2-1 is never a square, because the only squares that differ by 1 are {0,1} which aren’t attainable when n\ge 1.
  • n^2+3 is a square for only finitely many n, because the only squares that differ by 3 are {1,4}.

Exercises to try yourself

  • n^8, 3n+1, 3n-1, \lfloor \sqrt{n}\rfloor, 2^n, 2^n+1, 2^n-1, 3n^3, n^2+5n+10,
  • or, now with p ranging over the set of prime numbers: 3p^3.

Some discussion of some of these follows later to avoid spoilers.

BMO1 2023, Problem 4

This problem does not have exactly the same structure as the previous exercise. A solution will follow shortly, but before starting, [spoilers] I want to emphasise that the main part of the solution involves framing this problem exactly as in the exercise above.

  • We will establish that there are only finitely many n such that n\times 2^n+1 is a square, using a classical number theory argument.
  • In doing so, we will eliminate all integers n that are at least some threshold value K from consideration (which we think of as “n large”, even though in this case it isn’t so large).
  • The actual set of solutions comes from check the remaining “small” values of n.
  • The point to emphasise is that while this third bullet is definitely an important component of a successful solution (and does feel closest to actually addressing the “find all” aspect of the problem statement), it is not really the key step, since checking a small number of possibilities is fundamentally much more straightforward than an argument to eliminate the other infinitely-many integers.

This overall structure is very common when solving Diophantine equations involving integers, even if the exact statement isn’t “find all n such that […] is a perfect square”.

Anyway, to the solution of this problem. As in many problems of this difficulty in this number theory, it’s really useful to aim to factorise and analyse the factors, remembering that they are integers! In this case, writing n\times 2^n+1=k^2 doesn’t suggest an easy factorisation of the LHS, but rewriting as n2^n = k^2-1 does now have a nice factorisation, using difference of two squares on the RHS:

n2^n = (k-1)(k+1).

Here the two factors are (k-1) and (k+1). We know nothing about k, so we know nothing intrinsic about these factors, except that they differ by 2. But now when we consider that their product is n2^n, we can start to make some serious deductions4.

  • (k-1) and (k+1) differ by two, and so have the same parity5. Then n2^n is even, and so in fact both factors are even.
  • But more than this, one factor will be a multiple of 4, while the other will not be. So all the powers of 2 within n2^n (which may include additional factors of 2 coming from n) apart from one, must be included in one of the factors.
  • The idea is that 2^n is generally much larger than n, and so this will force one of the factors to be much larger than the other factor, which is not permitted. (Recall that the factors differ by 2.)

So formally, we might write that k+1\ge 2^{n-1} and k-1\le 2n. These are inequalities not equalities because some of the factors of n could be in (k+1) not (k-1) and/or a priori, we could have k-1=2^{n-1} and k+1=2n etc. This leads to

2n+2\ge 2^{n-1} (*)

and we now have exactly the language to describe the truth of this inequality! It is only true for finitely many positive integers n. There are a number of ways to prove this, but it is important that we do provide a lower bound. One possibility is to check that (*) holds for n=5, and then prove (*) for all n\ge 5 by an inductive argument.

At this point, we have shown that n\times 2^n+1 is not a perfect square for n\ge 5, and so at this point it really is easiest just to check n=1,2,3,4 by hand, which reveals that n=2,3 work.

To link this to the background, note that this final procedure of “finding all the solutions” really had nothing in common structure-wise with “solving 3x+4 = 2(x+7)“, for which substituting in various values of x would never constitute part of a good solution.

Comments on exercises

  • 3n+1 is a square for infinitely many n, while 3n-1 is never a square, for reasons that are often framed in the language of quadratic residues.
  • 2^n is a square for infinitely many n (specifically, when n is even), while 2^n+1 is a square only when n=3, which can be seen via a similar argument to the argument above for the BMO problem. Meanwhile 2^n-1 is never a square, which can also be checked using quadratic residues.
  • 3n^3 is a square for infinitely many n (specifically, when n=3k^2), while 3p^3 is a square for only one prime p, since only one prime is divisible by 3.
  • n^2+5n+10 is only a square for finitely many n, because when n is large, we have (n+2)^2< n^2+5n+10<(n+3)^2. This style of argument is sometimes called square-sandwiching, although it can of course be deployed in contexts other than squares. Problems that turn on this method have appeared in BMO surprisingly often in the past 15 years. For this particular example, note that one does have to check a handful of values to confirm it is for finitely many but at least one n (rather than for no n).

Footnotes

  1. of course, writing even more wrong is in itself making a nuanced comment about the parity of the prime numbers. ↩︎
  2. given a set A\subseteq \mathbb{N}, a natural formalisation of the notion that ‘most integers are not in A’ would be that \lim_{n\to\infty} \frac{|A\cap\{1,\ldots,n\}|}{n}=0. In other words, the proportion of elements of A amongst the first n integers vanishes as n\to\infty. This is certainly true when A is the set of cubes.
    There are many sets for which this limit does not exist, including quite natural sets like the integers whose decimal representation starts with a 1, and so a full treatment of this notion of asymptotic density would require more than a footnote. ↩︎
  3. in particular, we might wish to draw a distinction between f(n) is a square for infinitely many n and the stronger statement f(n) is a square for all-but-finitely many n, and in some applications that difference is crucial. ↩︎
  4. A common error is to make some reasonable-sounding assumption about how the factors of n\times 2^n are split between (k-1) and (k+1), for example by assuming that k-1=n and k+1=2^n because this is visually a natural way to pair them up. ↩︎
  5. parity refers to whether a number is odd or even. ↩︎

BMO1 2023

Posted on by
1

The first round of the British Mathematical Olympiad was marked in early December. Belatedly, here are some thoughts of the problems. These aren’t supposed to be official solutions, and some of them are not in fact solutions at all. Students reading this in future years are advised, as always, that such commentaries are normally more valuable after attempting and digesting the problem yourself first.

Note that the copyright to the problems is retained by BMO, and I’m reproducing here with permission. The paper can be found in its original format here.

Problem 1

I only have a few brief comments on this problem.

When you are asked to count some class of objects in a problem, it is common to make progress by rephrasing or recharacterising the objects you are trying to count. Often the recharacterised object may be more naturally suited to enumeration. As a slogan: do some thinking or apply some logic first, before starting counting.

However, when counting anything at all, make sure you read the question very carefully! There are some types of problem where misreading the problem will become obvious later. For example:

  • In a ‘prove that X is true’ question, you might find examples which fit your misreading, but where X is clearly not true!
  • In a geometry question, an accurate figure may be impossible if you assume the wrong pair of angles are equal, or you may end up proving something absurd, eg all triangles are equilateral.

But counting problems do not have this quality! Unlike a proof-based question, it always works as a problem to say count the number of […]. Whether it’s a good problem is another matter. Indeed, whether it is possible to get a nice answer may be hard to say. There are many natural combinatorial objects indexed by n which can’t be enumerated in closed-form (meaning as a single expression involving a combination of standard functions).

It would be a real shame to drop significant marks on this approachable P1 by instead answering (or wasting time struggling to answer) a different problem that carries no credit.

Problem 2

In the IMO programme, we discuss how the required conclusion of a problem might not be the most natural insight about the setup. Instead, the required conclusion might instead follow quickly from a much more natural fact which is not discussed at all in the problem statement. Especially in the context of geometry, this is often the crux of a good problem. Since we aren’t allowed to ask “say something interesting about this setup”, a well-structured problem might require the solver to investigate the setup and discover something interesting without prompting.

In this case, the investigation involves exploring the given recursion (for a_n in terms of a_{n-1},a_{n-2}) and noticing that it can be converted into a recursion for the increments a_n-a_{n-1} in terms of a_{n-1}-a_{n-2}. What makes this clever is that it works nicely but differently in the two cases. Note that because the conclusion involves ‘consecutive integers’ (ie where the increment is equal to 1), this is a clue that this is a good line of attack.

Specifically, we get a_n-a_{n-1}=a_{n-1}-a_{n-2} or a_n-a_{n-1}=2(a_{n-1}-a_{n-2}).

There has been no reference to a_{2023},a_{2024} or to the fact that the sequence is integer-valued, but now one can bring that back into focus. If a_{2024}-a_{2023}=1, this means that a_1-a_0=2^{-k} for some k=0,1,\ldots,2023. But a_0,a_1 are integers, and so the only option is a_1-a_0=1.

Problem 3

This is an excellent BMO1 easy geometry problem, and should be near the top of the list for students in future years who are practising this subject while preparing.

This is a good exercise in avoiding mindless angle-chasing. In general, most geometry problems at this difficulty level can be solved just by identifying pairs of equal angles, possibly with an occasional use of something like 180-\angle A or 90-2\angle A if there’s a clear geometrical meaning to those quantities.

One goal might be to prove carefully that triangle AXZ is isosceles with \angle A =\angle X. This, combined with ABX being isosceles, shows that ABXZ is a kite, and so BZ is perpendicular to AX, which is the same line as AC. (*)

And with so many isosceles triangles given in the construction, as well as other pairs of angles coming from the cyclic quadrilaterals, this equality of angles in isosceles AXZ can be handled as shown below, or in many other orders.

The equal red angles and equal green angles immediately show that \angle ZAX=\angle AXZ, since both are ‘180 minus red minus green’. Observe that because we’ve already handled a reduction to the problem at (*), this diagram didn’t actually need to have line BZ included, even though it’s part of the original conclusion!

A remark about diagrams: if you match angles efficiently eg as in the figure above, you will discover that triangle AXZ is isosceles even if it doesn’t look particularly isosceles on your figure. Similarly for CXY if you use that in your proof. However, if you draw an accurate figure using compasses, then depending on where the points end up, it may be very clear immediately from the diagram that these triangles are isosceles. This has good points and bad points:

  • Good point: from an accurate figure, it’s more likely that you’ll have the thought process along the lines of “Oh, so AXBZ must be a kite, and that explains why those lines are perpendicular, so I should prove the kite result.”
  • Bad point: it can be easy accidentally to assume one of these intermediate results before proving it. If you assume that CXY is isosceles, or something equivalent (like BCXY a kite, or X,Y are reflections in BC) this is likely to be viewed as a big hole in the proof, not much worse than assuming directly that AXZ is isosceles.

The configuration is intriguing at a broader level. If you extend BX to meet the circumcircle, you now have a cyclic hexagon where the diagonals meet at X and form three kites.

Problem 4

I submitted this problem, and a separate post is now available.

Problem 5

The wording of this problem follows a standard pattern, and the wording of a successful solution should also follow a standard template. If spending a few hours preparing for BMO1 or similar level competitions, it would be worth devoting an hour to problems of this sort, because they come up all the time.

A previous post has discussed the yellow and white houses from the MOG paper in 2018, which is similar in structure, but this P5 has more unusual constraints. Nonetheless, the principles of that post apply. A solution attempt must include a statement of the conjectured smallest number K of faults plus

  • a construction X showing that it is possible to have K faults
  • an argument explaining why K-1 is not possible.

Note that in general, an argument saying “start with X – you can’t remove any faults” will not be valid. After all, how do you know you haven’t missed some much better construction that is totally unrelated to X?

Whether it’s in a live competition or for practice, time spent investigating what K should be is essential. If you commit too early to a value of K that is too large, you certainly won’t be able to prove that K-1 is not possible!

Returning to the details of this question, the fact that the total number of dots is a multiple of 4 but not a multiple of 3 gives a clue that the optimal construction might be based on groups of 4. Probably many students will have found a repeating pattern of four colours that gives 250 faults in total. This is a plausible guess for the minimum.

There is one challenge in proving this, namely that the pattern RBBR has no faults within this group of four. However, it must create a fault at either end when you consider the next group of four on either side. So the key here is to index the faults by the left of the two affected dots (or, properly speaking, we should say the anticlockwise of the two affected dots, since they are on a circle). Then, one can justify, either by a reduction argument or by simply listing all 2^4=16 possibilities, that each group of four indexes at least one fault, which proves that the minimum is 250 as required.

Problem 6

This year, more participants than usual scored close to full marks on BMO1, but I don’t think it is fair to say that this particular problem was too easy. The harder part of the problem (proving that it is necessarily true for n odd) is relatively short. That doesn’t mean that it’s obvious, and there are many ways to go astray. I personally spent 20 minutes on the n odd case pursuing ideas that are hard to articulate but certainly did not work. It just means that it’s relatively unlikely that a contestant had the main idea but ran out of time to write it.

It’s crucial to establish the correct answer by trying various constructions. It’s possible that the octagon n=8 was more instructive than the hexagon n=6. It’s crucial to notice that if you start with a regular k-gon (for any k>2), you can ‘decorate’ each side with congruent ‘shallow isosceles triangles’ to get a 2k-gon that satisfies the length condition but doesn’t have equal angles.

One advantage of taking the isosceles triangle to be very shallow is that we can claim that when \theta is small enough, the 2k-gon is convex, and that the obtuse angle in the triangle is greater than the total obtuse angle at the vertices of the k-gon without formally justifying this with algebra.

Of course this approach does not make sense for constructing an n-gon when n is odd. But this is absolutely not a proof that there is no such construction for n odd. However, in the context of an olympiad problem at this level, it is reasonable evidence that the statement might be true for n odd.

The condition given about the lengths is a local condition, meaning that each condition only affects nearby vertices. When thinking about proving this result, one needs to consider whether we will find a local conclusion (eg two consecutive angles are equal), or a global conclusion (eg every angle is less than or equal to the ‘average angle’). This distinction is less clear when n is small, of course.

I won’t spoil the end of the problem, except to say that I wasted my 20 minutes thinking about global effects, whereas actually the main route involves a neat observation of the local situation.