Alice and Bob play the following number guessing game.

  • First Alice picks an integer $n$ with exactly $250$ positive divisors. These divisors include $1$ and $n$, and are denoted as $1=d_1<d_2<d_3<\cdots<d_{249}<d_{250}=n$.
  • Then Bob may query these divisors by paying a fee of $x$ Euro per query to Alice. Such a query simply consists of an index $i$ with $1\le i\le250$.
  • If Bob already knows the value of the divisor $d_{251-i}$ (since he has asked it in an earlier query, or since he is able to deduce it from the knowledge gained so far), then Alice answers the query with the word "BOOM".
  • If Bob does not know the value of $d_{251-i}$, then Alice answers the query with the value of $d_i$.
  • The game ends, as soon as Bob knows $n$ and announces it to Alice. Bob then receives $600$ Euros from Alice.

Question: What is the largest fee $x$, for which Bob can still avoid (with absolute certainty) to lose any money?

  • Don't you mean "What is the largest value of $n$"? – Paul Evans Mar 12 '16 at 15:15
  • @Paul Evans: No, the "largest value of x" is fine. (Bob pays x Euro per query.) – Gamow Mar 12 '16 at 15:15
  • oh hoo...alice and bob returns... :) – manshu Mar 12 '16 at 15:16
  • 2
    Hey you can waste your money if you ask for i=250.. It's a BOOM because you know d(1) = 1. So guys better use 1 < i < 250 – Varon Mar 12 '16 at 17:20
up vote 7 down vote accepted

Surely I am missing something.

I believe he needs two guesses.

The first guess

249. We know that $d_{2}$ is the smallest prime factor. We look at the factors of $d_{249}$ including itself and 1. There are two cases.

First case:

If $d_{2}$ is not a factor of $d_{249}$ then $d_{2}$ times every factor $d_{249}$ will be a new factor of n. Therefore, if there are 125 factors of $d_{249}$ then all we know is that $d_{2}$ is a prime number less than the smallest prime factor of $d_{249}$. Let the smallest prime factor of n be q. $d_{248}$ is n divided by q. We ask for this number and solve for $d_{2}$, the smallest prime factor of $d_{248}$.

Second case:

If there are more than 125 factors of $d_{249}$ then it must be that $d_{2}$ is a factor of $d_{249}$. We don't need a second question in this case. $d_{2}$ is the smallest prime factor of $d_{249}$.

Finally,

You can't do any better than asking for 249 because anything less than 250 misses at least one prime factor. Call it p. If it is unique, that is p squared is not a factor of n, then in the worst case you can only know what range p is in but not p itself.

We can see this as follows:

Consider the case where n has only two prime factors and n = $p_{1}$ * $p_{2}^{124}$. If $p_{1}$ < $p_{2}$, then only the even numbered divisors will contain $p_{1}$. If $p_{2}$ < $p_{1}$ < $p_{2}^{2}$ then only the odd numbered divisors will contain $p_{1}$. Therefore, whatever divisor we choose with our first guess we cannot guarantee that it will contain $p_{1}$. We can only know that it lies between successive powers of $p_{2}$. Since $p_{2}$ can be arbitrarily large, we cannot guarantee that only one prime lies in that range.

  • 1
    This does not work for the case 2 * 7^124. When you query d_249 it will be 7^124. After this you know all numbers, d3, d5, d7, d9, d11, etc. Therefore you cannot query any number which contains the factor of 2, because you know its inverse. You cannot query d2 because you know d249, You cannot query d248 because you know d3, etc. – Tony Ruth Mar 16 '16 at 21:11
  • @TonyRuth Absolutely right. Would you like to collaborate on a wiki answer? – Hugh Meyers Mar 16 '16 at 21:55
  • Sure, I would like to collaborate, but I'm not sure how to set up the wiki answer. The BOOM condition is very tricky, as it seems like there are a lot of ways to work yourself into a corner where you cannot ask any new queries. – Tony Ruth Mar 18 '16 at 16:57
  • @TonyRuth I haven't worked it all out myself. I got as far as figuring out that if you ask for any divisor greater than 26, you might find out it's 124, 1 distribution and be stuck as you pointed out. It ought to be solvable if you start small though. I'll try to find time to start a wiki answer and you can chime in as you see fit. – Hugh Meyers Mar 18 '16 at 17:06

You can solve for n in at most

1 questions. Therefore x = 600

Here is how this works:

First consider that n = $\prod_{j=1}^{k}\pi_j^{g_j}$ where $\pi_j$ is a prime number, $g_j$ is its multiplicity, and k is the total number of unique primes. The number of divisors is N = $\prod_{j=1}^{k}(g_j+1)$ Therefore $g_j$ = {1,4,4,4}; {1,4,24}; {1,124}; {4,4,9}; {4,49}; or {249} since N = 250. These are the possible multiplicities of the prime factors of n. I will query $d_{248}$.

Furthermore:

Let's consider the information gained by finding $d_{248}$ and factoring it. By comparing it to the multiplicity list above there are 2 possibilities, either the lowest prime number does not have multiplicity 1, and we will get multiplicities like = {1,4,4,2} Then obviously $n = d_{248} * \pi_4^2$. If the smallest prime number does have multiplicity 1 then we will get multiplicities like {1,3,4,4} and n = $d_{248} * \pi_2$ Therefore we know all the prime numbers and their multiplicities of the factorization of n.

example:

n = $2^4*3^4*5^9$ Then $d_{248} = 2^4*3^3*5^9$ We see that this list goes with the {4,4,9} possibility. Therefore the term with a multiplicity of 3 is one too low, and we conclude that n = $d_{248}*3$

Edit, I realized this does not work for the case n = $3^4 * 5 * 11^4 * 13^4$ because

$d_{248}= 3^4 * 11^4 * 13^4$ and you cannot determine what the missing factor is (5 or 7)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.