$15$, basically ask prime powers as follows: - if currently $p^k$ divides, ask $p^{k+1}$ - if does not divide, ask next prime start with $2$ Worst case w/ this algorithm is when number equals $1$, with $15$ questions asked

Induct to show that answer with $50$ replaced with $n$ is $\pi(n)$. Clearly at least these many are needed if William say announces he will pick a prime. For the upper bound, induct using Bertrand's postulate

Suppose the number is $n$, we claim that Victor needs to ask at least $\pi(50) = 15$ questions. He starts by asking $2$, and if at any point a prime $p^k \mid n$ ask $p^{k+1}$ and if not, then ask the next prime. It can be easily checked that this works. Now suppose there is a way in which Victor wins with $14$ questions but there are $15$ primes in between $1$ and $50$, so had William been thinking of the prime that Victor missed, Victor loses.

The answer is $15$ . There are $15$ prime between $1$ and $50$. So If we choose all the $15$ primes then we can easily find the number asked by William. Now let's suppose victor chooses $\le 14$ primes There will always be one prime missing so if William choose the prime which is not included or its multiple than victor will not be able to identify the number.Contradiction Thus $n=15$ is minimum

SaintBroseph wrote: The answer is $15$ . There are $15$ prime between $1$ and $50$. So If we choose all the $15$ primes then we can easily find the number asked by William. Now let's suppose victor chooses $\le 14$ primes There will always be one prime missing so if William choose the prime which is not included or its multiple than victor will not be able to identify the number.Contradiction Thus $n=15$ is minimum But then how to distinguish $2*3$ with $2^2*3$?

Also, I'm still unsure of what's wrong with my solution: We claim $23$ is the minimum, representing the $23$ prime powers smaller than $50$. Obviously, $23$ works, since you can find the exact exponent of each prime in the prime factorization of William's number. If Victor does not ask a question with $m=p^a$ for prime $p$ and $p^a \leq 50$, then there is no way to distinguish between William's $p^a$ and $p^{a-1}$.

Because $2^6 > 50$, the sum of the exponents can't be larger than $5$, so he won't need to test all powers (for example if $2$ doesn't divide $m$, he won't test $2^2, 2^3$, etc. Also, if $2$ divides, he doesn't need to test prime numbers larger than $23$, or else $m>50$.

Itzrageur wrote: Because $2^6 > 50$, the sum of the exponents can't be larger than $5$, so he won't need to test all powers (for example if $2$ doesn't divide $m$, he won't test $2^2, 2^3$, etc. Also, if $2$ divides, he doesn't need to test prime numbers larger than $23$, or else $m>50$. I see. So to figure out that $15$ is the worst case scenario for eliminating unnecessary prime powers, we would have to do casework (potentially starting with the divisibility by $2$ logic in your post)?

eduD_looC wrote: Itzrageur wrote: Because $2^6 > 50$, the sum of the exponents can't be larger than $5$, so he won't need to test all powers (for example if $2$ doesn't divide $m$, he won't test $2^2, 2^3$, etc. Also, if $2$ divides, he doesn't need to test prime numbers larger than $23$, or else $m>50$. I see. So to figure out that $15$ is the worst case scenario for eliminating unnecessary prime powers, we would have to do casework (potentially starting with the divisibility by $2$ logic in your post)? Well to figure out $15$ is the worst case scenario you can first show that if the number chosen is $1$, you will need to eliminate all $15$ prime factors between $1$ and $50$ to be sure that it is $1$. Then, you do the casework to show you never need more than $15$ guesses like you said.

Can someone please tell how to formally write up the proof of this problem in a contest, or even how to formalize it for ourselves. I intuitively feel the proof is fine, but sometimes I don't feel 100% sure about it.

Possibly the easiest OLY Problem ever... Took me ~15 seconds to solve. 0M..? $3$ min writeup. We claim that the maximum number of questions needed will occur only for a prime or 1. If the number is composite, there are $>1$ $m$ which will narrow, and thus, lead to a lower question amount to guarantee. Since there is one $1$, and $15$ primes, Victor must guess $15$ m's maximum to eliminate to only $1$ number. Thus, the answer is $15$

Amkan2022 wrote: Possibly the easiest OLY Problem ever... Took me ~15 seconds to solve. 0M..? $3$ min writeup. We claim that the maximum number of questions needed will occur only for a prime or 1. If the number is composite, there are $>1$ $m$ which will narrow, and thus, lead to a lower question amount to guarantee. Since there is one $1$, and $15$ primes, Victor must guess $15$ m's maximum to eliminate to only $1$ number. Thus, the answer is $15$ May you please provide more detail? I wasn't able to understand any of your statements.

Could the answer be 14? If Victor has asked for 2, 3, 5, 7, 11, 13, ... 43, and William answered "No" to all of those, then Victor already knows the answer is 47.

ugesaurio wrote: Could the answer be 14? If Victor has asked for 2, 3, 5, 7, 11, 13, ... 43, and William answered "No" to all of those, then Victor already knows the answer is 47. The number could also be 1

Redacted

Accept that the number is x which is we are searching. m is the divisor of x. m must be prime number. Assume that x is 47. Victor will ask m={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43} But he will not ask 47, because, after asking all of the another prime numbers, he will know that it's prime number and also one of them will left. And he will guess. So the answer will be 15 .

Answer = $15$ There are $15$ prime numbers less than 50, and so we can in any case select all $15$ primes and find William's number. [worst case] The algorithm is as follows: - start with 2 - Ask for a prime $p^\alpha$ , if it divides, then ask if $p^{\alpha+1} \mid n$ - if $p^\alpha \nmid n$, ask for the next prime

Claim: The answer is $15$. Proof: Notice that there are $15$ primes from $1$ to $50$. It is very easy to notice that if the desired number is $47$ or $1$, then only Victor will take $15$ turns. Now if the number William chose a number divisible by $2^k$ then we would not need to check for as many primes in which case the least number of attempts would be less than $15$ . Notice that this number keeps on decreasing if the number William has chosen is divisible by $3^k$ and so on....