Guessing a number with 250 divisors

Question

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?

Answer 1

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.

Answer 2

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)

Answer 3

There is no strategy that is guaranteed to ever win, thanks to the BOOM rule.

If Alice picks $N = a^{124}\times b$, with $a$ and $b$ distinct primes, then $N$ has 250 factors. Bob's challenge is to determine $a$ and $b$.

The problem is that if he determines the order of the factors before determing both $a$ and $b$, then the BOOM rule can prevent him from ever learning $b$.

For example, if he asks for $d_{50}$ and gets back $3^{25}$, then he knows that $N = 3^{124}\times b$, and that $b = 5$ or $b = 7$. He also knows that all the even-indexed factors (up to 248) are $d_{2i} = 3^i$ and odd-indexed factors after $1$ are $d_{2i+3} = 3^i\times b$. And of course, he knows $N = d_{250} = 3^{124}\times b$.

If he ever asks about any odd-indexed factor (other than 1), he gets a BOOM, because he knows the corresponding other factor. For example, he knows that $d_{248} = 3^{124}$, so if he asks about $d_3$, he gets a BOOM. Thus, he can never determine whether $5$ or $7$ is the other factor.

This extends generally to the case where $a^k < b < a^{k+1}$. If he asks about a factor (where $i \leq k$, $j \geq 0$), then the answer will be:

$$ d_{i} = a^{i-1}$$ $$ d_{250-i} = a^{124-i}\times b$$ $$ d_{k+2j+1} = a^{k+j}$$ $$ d_{k+2j+2} = a^j \times b$$

If he somehow determines $k$ before he determines $b$, then he has determined half the factors. He can't ask about the other half, because of the BOOM rule. Specifically, he can't ask about any factor containing $b$, so he can't ever determine $N$.

The only way to be sure he doesn't determine $k$ before $b$ is to start at $d_2$ and ask about each one going up. Unfortunately, if he gets to $d_{125} = a^{124}$, then he has lost because it must be that $b > a^{124}$ and all the remaining factors are just $b$ times the ones he's already gotten.

Thus, there is no strategy that guarantees a win in any number of turns.

Update: Alice could have picked $N = a^{249}$ instead, as that also has $250$ factors. Bob would not know which after asking about $d_2$ up to $d_{125}$. Unfortunately, he still can't ask about any factor past number $126$, so he's still sunk.