A friend of mine recently sent me the following math problem.

There is a teacher and 2 students in a classroom. The students are A and B. The teacher thinks of 2 positive integers and tells the sum of those numbers to student A without student B hearing it. Then tells their product to student B without student A hearing it. After this, the teacher asks the 2 students what was the 2 numbers.

First student A says: I donâ€™t know.

Then student B says: I donâ€™t know either.

After hearing this, student A says: Now I know.

Then student B says: Now I know them too.

What were the 2 numbers?

As an extension:

What if the two numbers must be unique? That is, both students know the numbers must be unique?

If you donâ€™t want to have the answer spoiled (or at least, my version of the answer), donâ€™t read the next paragraph! Iâ€™m going to write some about how I approached it. Here is a diagram of the problem statement.

This can be broken down into four steps. Letâ€™s give student A the number $P$ and student B the number $Q$.

- Student A canâ€™t figure out the two numbers. This means that $P$ must have more than one additive decomposition $P = x + y$, where $x$ and $y$ are positive integers. Fortunately almost every positive integer satisfies this property, except for
`1`

(which has no additive decompositions) and`2`

and`3`

(which have exactly one each,`1 + 1`

and`1 + 2`

). - Student B canâ€™t figure out the two numbers as well. This means that $Q$ must have more than one multiplicative decomposition $Q = x y$. This means that $Q$ cannot be a prime number; otherwise, student B would be able to figure out the answer.
- After hearing that Student B canâ€™t figure out the number either, Student A realizes that the number must not be prime. This means that Student A can rule out any additive decompositions of $P$ which consist of a prime number plus 1. Since they are able to figure it out afterwards, there must be exactly one pair left over.
- After hearing that Student A has figured out the answer, Student B can rule out any additive decomposition which wouldnâ€™t have been ruled out by the second step.

I am pretty lazy and a mediocre mathematician, so rather than trying to figure it out mathematically, I decided to figure it out through code. I also think putting it in code makes it a bit clearer. So letâ€™s code up each step and test out some numbers!

Letâ€™s define a helper function for creating a unique tuple from two numbers. This will ensure that we donâ€™t accidentally double-count pairs.

We can use the following function to find all of the additive decompositions for some number.

We can use the following function to find all of the multiplicative decompositions for some number.

For Student A to be unable to figure out the first number, there must be at least two additive decompositions.

For Student B to also be unable to figure out the first number, there must be at least two multiplicative decompositions (which also pass the first step).

After Student B has announced they are unable to figure out the answer either, Student A can rule out any pair which would have let Student B figure out the answer.

Finally, now that Student A has announced they are able to figure out the answer, Student B can rule out any pair which would not have let Student A figure out the answer.

Notice that a lot of these functions are called multiple times with the same inputs. We can *memoize* the function calls, since they always return the same value, using the following function.

We can string all of these functions together and search through all the possible pairs from 1 to 5.

This gives the results for all the pairs from 1 to 5:

What if the two numbers must be unique? That is, both students know the numbers must be unique?

This can be done by modifying two small parts of the program.

This gives the results for all the pairs from 1 to 5:

Resume Github Twitter Email Feed Directory Home uBlock