As this was the second question that we used in the CS interview at LMH in December 2018, it was chosen to be a shorter question. Nevertheless, as the discussion below suggests, there was plenty of opportunity to have an interesting conversation about it. The question below is from this post.

Question: For a non-negative real number \(x\), the floor of \(x\), denoted by \( \lfloor x \rfloor\) is the largest integer that is less than or equal to \(x\). For example, \(\lfloor 3 \rfloor = 3 \) and \( \lfloor 6.999 \rfloor = 6 \).

  1. Let \(n\) be a positive natural number that is a perfect square. You are asked to pick a set of \( \left\lfloor \frac{n}{2} \right\rfloor \) natural numbers from \( 1,2, \ldots,n -1 \), such that none of the chosen numbers is a perfect square, and no two distinct chosen elements add up to \(n \). For what values of \(n\) is this possible?
  2. Let \(n\) be a positive natural number that is a perfect cube. You are asked to pick a set of \( \left\lfloor \frac{n}{2} \right\rfloor \) natural numbers from \( 1,2, \ldots,n -1 \), such that none of the chosen numbers is a perfect cube, and no two distinct chosen elements add up to \(n\). For what values of \(n\) is this possible?

Solution: We pair the numbers from \(1, 2, \ldots, n - 1, \) as, \[ (1, n - 1), (2, n - 2) , \ldots, \left(\left\lfloor \frac{n}{2} \right\rfloor, \left\lceil \frac{n}{2} \right\rceil \right). \] Observe that depending on whether \(n\) is odd or even, the last pair is either \( ((n - 1)/2, (n + 1)/2) \), or \( ( n/2, n/2) \).

We notice that there are exactly \( \left\lfloor \frac{n}{2} \right\rfloor \) pairs and we can't pick both numbers from a pair to be in our target set \(S\) as they would add up to \(n\).

Now for the first part, it would pose no problem unless both numbers in a pair were perfect squares, as in that case we would be prevented from putting either of those in \(S\). Can this happen? Recall that \(n\) itself is a perfect square so let us write \(n = c^2 \). Suppose one of the pairs was \( (a^2, b^2) \), then we have \[ a^2 + b^2 = c^2. \] This happens when \((a, b, c) \) is a Pythagorean triple. So, we can conclude that (for the first part) the task of picking such a set \(S \) is possible for all \(n\) that are perfect squares, provided \( \sqrt{n} \) is not the largest number of a Pythagorean triple.

The second part is very similar. Let us write \(n = c^3 \). The problem arises if there is a pair of the form \( (a^3, b^3) \), and it holds that, \[ a^3 + b^3 = c^3. \] Fermat's Last Theorem states that no such numbers \(a, b, c \) exist. So in fact, it is possible to do the task for all \(n \) that are perfect cubes.

Discussion

Although the solution is short and elegant, you can see that the problem requires a mix of combinatorics and number theory. This is quite typical of questions that you can expect in interviews or on the MAT. We want to see how you make connections between different areas of mathematics that you may have learnt, without being explicitly prompted to do so.

At this point I should say very clearly that we don't actually care about whether you know what Pythagorean triples are, or if you have heard of Fermat's Last Theorem. It is likely that most students we are interviewing know the former and have at least heard of the latter, but that is not the point of the question. What we are mainly looking for is your ability to find ways to attack an unseen problem and make logical arguments.

In a typical interview, it would be quite common for candidates to begin by considering small values of \(n \). The idea of trying out small cases before trying to answer any question in generality is an important one in mathematics, and if it seems to me that you are not already acquainted with it, I would, very soon in the interview, make that suggestion.

When \( n = 1\), there is nothing to do. The next number to try is \( n = 4 \); we need to pick \(2 \) elements. We might begin by crossing out numbers that we cannot pick as they are perfect squares, and circle the ones that we can pick. This immediately yields the solution \(S = \{2, 3 \} \).

\[ \require{enclose} \enclose{updiagonalstrike}{1}, \enclose{circle}{2}, \enclose{circle}{3} \]

For \( n = 9 \), we can start the same way, we write all the numbers, \(1, 2, \ldots, 8 \), and cross out the perfect squares. \[ \enclose{updiagonalstrike}{1}, ~ 2, ~ 3,\enclose{updiagonalstrike}{4}, ~ 5, ~ 6, ~ 7, ~ 8 \] We might start picking the numbers left to right, circling them and striking out any number ruled out after picking one, e.g. picking \(2 \) rules out \(7\), and so on. We are left with, \[ \enclose{updiagonalstrike}{1}, \enclose{circle}{2}, \enclose{circle}{3}, \enclose{updiagonalstrike}{4}, \enclose{circle}{5}, \enclose{horizontalstrike}{6}, \enclose{horizontalstrike}{7},\enclose{circle}{8}. \] So we have the \(4 \) element set \(S = \{2, 3, 5, 8 \} \), which is exactly of the required size. This suggest an algorithm: we can first strike out all the perfect squares from \(1, 2, \ldots, n - 1\) (using a diagonal strike, e.g. \( \enclose{updiagonalstrike}{1} \)), then start picking from left to write and striking out (horizontally, so for \(n = 9 \), after picking \(2 \), we can rule out \( 7\) as \( \enclose{horizontalstrike}{7} \)) any number that is ruled out after we have made some choices. This worked in the case of \( n = 9 \). We can see below that it also works for \( n = 16 \). \[ \require{enclose} \enclose{updiagonalstrike}{1}, \enclose{circle}{2}, \enclose{circle}{3}, \enclose{updiagonalstrike}{4}, \enclose{circle}{5}, \enclose{circle}{6}, \enclose{circle}{7}, \enclose{circle}{8}, \enclose{updiagonalstrike}{9}, \enclose{horizontalstrike}{10}, \enclose{horizontalstrike}{11}, \enclose{circle}{12}, \enclose{horizontalstrike}{13}, \enclose{horizontalstrike}{14}, \enclose{circle}{15} \]

Detour: At least in good interviews, it was quite common to get to this stage, but then when probed to think whether the algorithm would always work, students would start using ideas like always pick numbers less than \( n/2 \) first so that no two of them would add up to \(n \). (Indeed, alternatively one could pick numbers that are great than \( n/2 \).) From the examples above, it is clear that always picking numbers on one side of \( n /2 \) doesn't work in general, because after crossing out perfect squares, there aren't enough of them left. The algorithm above, which goes left to right essentially picks as many numbers less than or equal to \( n /2 \) as it can, and then tries to make up for the missing ones by picking numbers that are greater than \( n/2 \). When probed whether this is always possible, some students jumped to the clean solution given above that involves pairing numbers that add up to \(n \), and at that point, realised the connection between Pythagorean triples and the question. Others, including some who got offers at Oxford, may have needed to work out the case of \(n = 25 \) in full detail. Luckily, while somewhat tedious, it is still just about possible to write all the numbers from \( 1\) to \(24 \) and then work out the details.

Back to the Discussion: Let us see what happens when \( n = 25 \). We can run the procedure described above to get, \[ \enclose{updiagonalstrike}{1}, \enclose{circle}{2}, \enclose{circle}{3}, \enclose{updiagonalstrike}{4}, \enclose{circle}{5}, \enclose{circle}{6}, \enclose{circle}{7}, \enclose{circle}{8}, \enclose{updiagonalstrike}{9}, \enclose{circle}{10}, \enclose{circle}{11}, \enclose{circle}{12}, \enclose{horizontalstrike}{13}, \enclose{horizontalstrike}{14}, \enclose{horizontalstrike}{15}, \enclose{updiagonalstrike}{16}, \enclose{horizontalstrike}{17}, \enclose{horizontalstrike}{18}, \enclose{horizontalstrike}{19}, \enclose{horizontalstrike}{20}, \enclose{circle}{21}, \enclose{horizontalstrike}{22}, \enclose{horizontalstrike}{23}, \enclose{circle}{24}. \] If we count them up, we see that we've only ended up with \( 11 \) numbers circled rather than \(12 \) as we might have hoped for. Among the numbers, \(1 \) through \(12 \), \(1, 4 \) and \(9 \) were crossed out as they were squares. The were paired with \(24, 21 \) and \(16 \) respectively. Picking \(24 \) and \(21 \) to go in our set doesn't pose a problem, as they are not perfect squares. But, we can't pick \(16 \) as it is a perfect square. The fact that \( 9 + 16 = 25 \), or \(3^2 + 4^2 = 5^2 \), poses a problem as we have two square numbers that add up to \(25, \) which itself is a perfect square.

For students who get to this point, usually it would be clear what the answer is, possibly with some help from the interviewers (which is perfectly fine!). For the second part, once the main argument has been understood, it is only a matter of knowing whether a solution to \( a^3 + b^3 = c^3 \) exists for positive integers \(a, b \) and \(c \). Fermat's Last Theorem rules out this possibility.

If there were time time left, I would explore further by asking students to count the number of ways in which picking such a set could be achieved. In general, once a solution is arrived at it is quite common for interviewers to start discussing related questions provided there was time remaining.

Reflections: The aim of this question is not to test whether students are familiar with Pyathagorean triples or Fermat's Last Theorem. What I was looking for is to see how students make a connection between two potentially interacting constraints, that the numbers picked should not be squares and no two of them should add up to \( n \). In good interviews, this naturally led to a quick chat about Pythagorean triples (which you should read about if you are not familiar, because they are cool) and a very quick word about Fermat's Last Theorem. The interaction between combinatorics and number theory that appears in this question is something that will be typical of questions you might get in interviews (or indeed on the MAT), as we are interested to see how you make connections between different areas of mathematics.