Sample interview problems

Suppose you start with the number ‘$a_1a_2..a_nb_1b_2...b_k$’ for some $b_i$s.

Suppose $m^7<$ ‘$a_1a_2..a_nb_1b_2...b_k$’ $<(m+1)^7$. Can you adjust the code to make it a $7$th power?

$\log_{10}($a number$)\approx$ the number of digits of the number.

We need the code to satisfy both (ii) and (iii). One option is to start with a $7$th power and then hope it contains the string ‘$a_1a_2...a_n$’. However, there is no easy way to control the digits of the $7$th power of a number: if we start with $321$ (say), the only way to tell what digits its $7$th power includes is to calculate it, at which point we are just guessing.

Instead, therefore, let us start with a code satisfying (ii) and try to make it satisfy (iii). Take ‘$a_1a_2..a_nb_1b_2...b_k$’ to be our code, for some $b_i$s and $k$. We want this to be a $7$th power but it probably won't be. Let's say instead that $m^7<$ ‘$a_1a_2..a_nb_1b_2...b_k$’ $<(m+1)^7$.

Crucially, while this code is not yet a $7$th power, it is pretty close. As the $b$s are irrelevant to whether or not the code works, we can try to adjust them to make the code a $7$th power by adding whatever its difference from $(m+1)^7$ is.

The only problem is that by adding this difference, we may be affecting some of the $a$s; we need the difference to be small enough not to impact them. So that we can add as large a quantity as possible, without disrupting the $a$s, take all the $b$s to be $0$ so the code is ‘$a_1a_2..a_n00...0$’ with $k$ $0$s after $a_n$.

We want the difference we are adding to affect at most the first $k$ digits of the code, so we want the difference itself to have at most $k$ digits. Similarly, we know $m^7$ and $(m+1)^7$ have (roughly) $n+k$ digits. Note that $\log_{10}($a number$)\approx$ the number of digits of the number; the error is always $\leq1$.

So we know $\log_{10}m^7=7\log_{10}m\approx n+k$ and we want $\log_{10}((m+1)^7-m^7)<k$. But $\log_{10}((m+1)^7-m^7)=\log_{10}(7m^6+21m^5+...+1)<\log_{10}(7m^6+m^6+...+m^6)$ for large enough $m$. This is $=\log_{10}(13m^6)=\log_{10}(13)+6\log_{10}m\approx 6\log_{10}m$ because $\log_{10}(13)\approx1$ which is negligible for large $m$. So we want $6\log_{10}m<k$ and $7\log_{10}(n+k)\approx n+k$.

Many solutions will work. For example, let's take $k=6.5\log_{10}m$ and $n=0.5\log_{10}m$. Then, by eliminating $m$, we find $k=13n$. Therefore, if we take ‘$a_1a_2...a_n00...0$’ where there are $13n$ $0$s following $a_n$, then we can add an adjustment to make our code a $7$th power without affecting the $a$s, meaning we get a code that works, regardless of the string ‘$a_1a_2...a_n$’. In fact, as can be readily seen, there are infinitely many codes that work.

Can you write a rock-solid argument to prove this by dealing with the approximations (like $\log_{10}($a number$)\approx$ the number of digits of the number) rigorously?

Suppose condition (iii) is changed so that instead of a $7$th power, we want the code to $=c_nx^n+c_{n-1}x^{n-1}+...+c_o$ for integers $c_i$ and $x$. Can you adapt the argument?

What if, instead of polynomials, we require the code to be within $1$ of $e^x$ for an integer $x$?

$0^2+2^2+(1+\sqrt{3}i)^2-0-2(1+\sqrt{3}i)-0=4+1+2\sqrt{3}i-3-2-2\sqrt{3}i=0$ as desired.

What effect do different transformations have on the equation $a^2+b^2+c^2-ab-bc-ca=0$?

By enlarging, rotating and translating the triangle in part (i), we can get any other equilateral triangle. Enlarging and rotating correspond to multiplying $a$, $b$ and $c$ by a complex number. But if $a^2+b^2+c^2-ab-bc-ca=0$ then $(xa)^2+(xb)^2+(xc)^2-(xa)(xb)-(xb)(xc)-(xc)(xa)=0$, as we can just divide through by $x^2$, so these transformations won't make the left-hand side of the equation non-zero.

Similarly, translating corresponds to adding a complex number.

\[(x+a)^2+(x+b)^2+(x+c)^2-(x+a)(x+b)-(x+b)(x+c)-(x+c)(x+a)=3x^2+2xa+2xb+2xc+a^2+b^2+c^2-3x^2-xa-xb-xb-xc-xc-xa-ab-bc-ca=a^2+b^2+c^2-ab-bc-ca=0\]

so again, this transformation won't make the left hand side of the equation non-zero.

Therefore, since our initial triangle satisfies the equation, and we can transform it into any other (equilateral) triangle while still satisfying the equation, every equilateral triangle in the plane satisfies the equation.

Hold $b$ and $c$ fixed, and consider the equation $a^2+b^2+c^2-ab-bc-ca=0$

Hold $b$ and $c$ fixed. Then $a^2+b^2+c^2-ab-bc-ca=0$ is a quadratic in $a$ so has at most two solutions. But there are exactly two equilateral triangles that can be formed from $b$ and $c$ (by putting $a$ on either side of the line connecting $b$ and $c$) and, by part (ii), both of these satisfy the equation so they are the two solutions so the equation has no more solutions.

Therefore, every solution to $a^2+b^2+c^2-ab-bc-ca=0$ corresponds to an equilateral triangle.

Where has the condition that $a$, $b$ and $c$ are distinct been relied upon?

Would this approach work if we were given an equation for a square? Why or why not?

Consider the Fibonacci sequence modulo $p$.

Will the sequence modulo $p$ repeat?

Can you show that the sequence modulo $p$ must repeat from the start?

Consider the Fibonacci sequence modulo $p$.

When working in modular arithmetic, it is often useful to look for repetitions. Here, suppose you choose a pair of numbers $(a,b)$ which are consecutive in the Fibonacci sequence (with $0\leq a,b<p$ since we are using modular arithmetic). Notice how one pair totally determines what follows (since the next term is their sum, etc). Then, as there are only finitely many ($p^2$) such pairs, the sequence of pairs must repeat at some stage. When it does, the sequence of pairs between the two repeats itself repeats over and over (since, again, one pair totally determines what comes next).

Clearly, then, we need to make sure one of the pairs in that repeating segment contains $0$, so that $0$ will occur infinitely often. The sequence starts with $0$ but this isn't enough, since there could be an initial segment and then the segment that repeats, like in $0.12\overline{34}$. We would like to rule this possibility out.

To do so, realize that each pair, as well as determining what goes after it, also determines what comes before it (as $F_{n+1}-F_n=F_{n-1}$). This reversibility means that, if $(a,b)$ is a pair that repeats, before each $(a,b)$ there must come a (new) $0$, since one comes before the first $(a,b)$ and each pair determines exactly the sequence that precedes it.

Hence, the Fibonacci sequence modulo $p$ repeats from the start and so includes $0$ infinitely many times, meaning the original Fibonacci sequence has infinitely many numbers that are divisible by $p$.

This is a relatively hard problem, because some of the ideas are non-obvious unless you see them. However, remember that in an actual interview, you will receive help from the interviewer so no problem will be quite as hard as it appears on your own.

Show that terms divisible by $p$ occur at a constant frequency. Hence, show there are infinitely many terms in the Fibonacci sequence that are coprime to (that is, share no prime factors with) all preceding terms.

Prove that any sequence of integers, starting with $0$, with a recursive rule defining it (where the next term is defined by the terms preceding it) has all the same properties.

For a point $(x,y)$, the sum of the distances is $\sqrt{(x+1)^2+y^2}+\sqrt{(x-1)^2+y^2}=r$. Squaring and rearranging, $r^2-2x^2-2y^2-2=2\sqrt{(x^2+y^2+1-2x)(x^2+y^2+1+2x)}$

Dividing by $2$ and squaring again, we find $(\frac{r^2}{2}-x^2-y^2-1)^2=(x^2+y^2+1)^2-4x^2$.

Rearranging to exploit the difference of two squares, $4x^2=\frac{r^2}{2}(2x^2+2y^2+2-\frac{r^2}{2})$.

Expanding and simplifying, $(r^2-4)x^2+r^2y^2=r^2(\frac{r^2}{4}-1)$

The sketch should be an ellipse, which is a circle stretched in one direction.

Consider the $n$-gon with maximum area for a given perimeter.

Focus on three consecutive points $A$, $B$ and $C$.

Assume we have the $n$-gon with maximum area; doing so let's us deduce properties of that $n$-gon.

Then focus in on three successive point, $A,B,C$. Hold $A$ and $C$ fixed, but let $B$ vary. It must have a fixed sum of distances from $A$ and $C$ so it can move along an ellipse with one axis the line $AC$ extended.

In doing so, it forms a triangle with varying area. We can calculate this area as $\frac{1}{2}$base$\times$height. But the base is constant ($AC$) so we simply need to choose the point that maximizes the height. From the shape/symmetry of an ellipse, this occurs when $B$ lies on the perpendicular bisector of $AC$ (compare with your sketch) so when $AB=BC$.

Since we were considering the $n$-gon with maximum area, its point $B$ must have already been in that place, so the two sides must be equal. Since this works for any three consecutive vertices of the $n$-gon, all sides of the $n$-gon are equal.

Why does this not imply that a regular $n$-gon is best?

In fact, a regular $n$-gon is best, but the proof of it is significantly harder; you can look online if interested.

Given that a regular $n$-gon is best, can you use this to conclude that a circle is the shape that maximizes the area for a given perimeter? Why or why not?

Only $2$ cops are needed. Now prove this number is necessary and sufficient to catch George.

Clearly, at least $2$ cop cars are needed, since George can always move in at least two directions, so he could always escape one car.

In fact, $2$ cars suffices. For a strategy, we need to confine George into progressively smaller sections of the grid without him breaking out. To do this, we can have one cop (cop $A$) responsible for keeping him trapped while the other cop (cop $B$) closes in on him.

Playing around with the problem with this in mind should be enough to discover the following strategy:

Initially, let cop $A$ move along the top road from right to left until he has the same $x$ coordinate as George. Then, let him copy George's movements in the $x$ direction. This prevents George from passing this blocking cop.

Then, cop $B$ acts as a beater, by moving along the next road down from right to left until his $x$ coordinate is the same as George. Then, he becomes the new blocker while cop $A$ takes over beating duties on the next road down. Repeating in this manner, they will eventually trap George into the bottom left corner and catch him.

How can we apply the idea of part (i) to this new situation?

In $3$D, we find at least $3$ cops are needed, through a similar argument as in part (i).

In fact, only $3$ are needed. For a strategy, we will want to repeat the same idea as before to trap George but the third dimension adds difficulties.

The solution is to restrict him one $2$D slice at a time. On the first slice, the two cops can, through the strategy in part (i), get to the same $x$ and $y$ coordinates as George, though not the same $z$ coordinate.

Then, leave one cop as a blocker in this slice and the other two can move onto the next slice to act as beaters.

Repeating this, eventually they will catch George in the final slice.

Can you see how this would generalize to higher dimensions?

You could also consider how the result would change if George's car was $a$ times quicker than the cops, or if the cops had to catch George in a certain time (e.g. supposing the statute of limitations for bank robbery expires after an hour) but solving these problems in general is non-trivial and, to my knowledge, hasn't been done.