Competition problem — Combinatorics

Library / /377 of 377

Combinatorics Difficulty 6.0 National Olympiad Prove it United States

Problem:

Two mathematicians, Kelly and Jason, play a cooperative game. The computer selects some secret positive integer $n < 60$ (both Kelly and Jason know that $n < 60$ , but they don't know what the value of $n$ is). The computer tells Kelly the unit digit of $n$ , and it tells Jason the number of divisors of $n$ . Then, Kelly and Jason have the following dialogue:

Kelly: I don't know what $n$ is, and I'm sure that you don't know either. However, I know that $n$ is divisible by at least two different primes.

Jason: Oh, then I know what the value of $n$ is.

Kelly: Now I also know what $n$ is.

Assuming that both Kelly and Jason speak truthfully and to the best of their knowledge, what are all the possible values of $n$ ?

Solution

Solution:

The only way in which Kelly can know that $n$ is divisible by at least two different primes is if she is given $0$ as the unit digit of $n$ , since if she received anything else, then there is some number with that unit digit and not divisible by two primes (i.e., $1, 2, 3, 4, 5, 16, 7, 8, 9$ ). Then, after Kelly says the first line, Jason too knows that $n$ is divisible by $10$ .

The number of divisors of $10, 20, 30, 40, 50$ are $4, 6, 8, 8, 6$ , respectively. So unless Jason received $4$ , he cannot otherwise be certain of what $n$ is. It follows that Jason received $4$ , and thus $n = 10$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.