Problem 887

[haroldgparker]

I'm having trouble understanding Problem 887. (https://projecteuler.net/problem=887)

Re: "Let Q(N, d) be the least number of questions needed to find any secret number from the set {1, ..., N} where no more than x+d questions are needed to find the secret value."

How does the result of Q(N, d) have anything to do with the restriction? If I'm given an N, and as it turns out, I need f(N, x) questions to establish that x is the secret value, then d = f(N, x) - x, but if I'm given some d from the outset, I don't see how there's anything I can do to make f(N, x) such that it's within d of x. I don't understand how d can be stipulated and how that stipulation could affect question asking strategy.

[wim59]

I respectfully second the opinion that this is a very poorly-worded question...

[Patryqss]

I also don't understand this problem. How the number of questions could possibly be larger than ceil(log2(N))? How can we limit or change the number of needed questions and what does it even mean?

An easy example that explains the rules in a better way would be very much appreciated

[mdean]

It took me a while to get it, but I think I comprehend it now. For the d=0 example, it means if the secret number is 1, you must determine it in 1 question. If you can understand that, you should be able to understand the given value of Q(N,0).

I'm hoping this will be treated as the bare minimum to understand an incomprehensible problem and not a spoiler.

[haroldgparker]

Thanks, mdean, I think I get it now.

[wim59]

Well, I eventually worked my way through the problem, but I would suggest to add the underlined section in the following excerpt for improved clarity:

"Let Q(n,d) be the least number of questions needed for the strategy that can find any secret number from the set {1,...,N} where no more than x+d questions are needed to find the secret value x."

[urimend]

Thanks @wim59, the phrasing was changed according to your suggestion.

[wim59]

@urimend: Great, thanks for taking notice!

[PierrotLeFou]

I'm blind and I have problems with texts between dollar signs "arithmetic expressions".
Can anyone just rewrite question 887 either in words or program-like form?
Thanks in advance.
BTW the ideal form of a binary search is when $n = 2^k - 1$.
I think I have somewhere a code to compute both the maximum and average number of iterations to find an element in a sorted list of numbers.
Example with numbers 1 to 7:
it takes 1 iteration to get 4, 2 to get 2 and 6, 3 to get 1, 3, 5, 7.
With 1 to 8, it will take 1 extra iteration to get the 8.

[heteroing]

Can anyone just rewrite question 887 either in words or program-like form?

Here's my attempt:

Consider the problem of determining a secret number between 1 and N inclusive by repeatedly choosing a number y and asking "Is the secret number greater than y?".

If N is 1, then no questions need to be asked. If N is 2, then only one question needs to be asked. If N is 64, then six questions need to be asked. However, in the latter case if the secret number is 1 then six questions still need to be asked. We want to restrict the number of questions asked for small values.

Let Q(N, d) be the least number of questions needed for a strategy that can find any secret number between 1 and N inclusive where no more than x + d questions are needed to find the secret value x.

It can be proven that Q(N, 0) = N - 1.
You are also given that Q(7, 1) = 3, and Q(777, 2) = 10.
Find the sum of Q(N, d) over all d between 0 and 7 inclusive, and all N between 1 and 7^10 inclusive.

[PierrotLeFou]

Thanks @heteroing
I now clearly understand the "text" of the question, but I'm not sure to agree with the results
As an example: Q(7, 0) would also give 3, not 7 or 6
For me the best strategy is to perform a binary search on a "virtual" list of numbers from 1 to N.
If N=7, number 2 is at position 1,etc.
By doing a binary search, I indeed find that Q(7, 1) =3. But Q(777, 2) gives me 9, not 10
And I disagree with Q(N, 0) = N-1. It's rather int(log2(N)). Same result for any number greater than N.
There is also a relationship for values ranging between different powers of 2.
I didn't check but Q(16, 1) should be 1 more than Q(8, 1).
What about numbers between 8 and 15 vs those between 16 and 31?
It seems that I don't still understand

Let Q(N, d) be the least number of questions needed for a strategy that can find any secret number between 1 and N inclusive where no more than x + d questions
are needed to find the secret value x.

[heteroing]

For Q(N, 0), we want the optimal number of questions to ask, such that if the mystery value is x, we locate it in no more than x questions. So we must locate x = 1 in only one question, which means we need to ask "Is the secret number greater than one?" as no other question can determine this value so quickly. We are forced to ask lots and lots of questions and not simply binary search, because we have to find small values of x very very quickly.