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 \( \lfloor \frac{n}{2} \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 \( \lfloor \frac{n}{2} \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?
This question was used in CS interviews at Lady Margaret Hall in December 2018.

Update: This post was updated to use MathJax on July 10, 2022.