I was given an interesting problem that comes in two parts.
In front of you is a treasure chest containing \$1000 with a 6-digit combination lock. You have to pay a constant amount for each time you change a digit. What is the maximum amount you are willing to pay per turn?
Not sure if my approach here is correct: if the expected value of the game is $E$ and the amount I pay per turn is $x$, then $$E=\frac{1}{10^6}(1000-x)+\frac{10^6-1}{10^6}(E-x)$$ $$=E\left(1-\frac{1}{10^6}\right)+\frac{1000}{10^6}-x.$$ $$\Rightarrow E=1000-10^6x.$$ For positive payoff, we require $x<1000/10^6$, i.e. we want to pay less than \$0.001.
My main issue is with the next subproblem.
When two or less digits are correct, an LED on the chest glows red. When three or more (but not six) digits are correct, the LED glows yellow. When all digits are correct, the LED glows green and the chest opens. Is there an optimal strategy? How much are you willing to pay per turn now?
How exactly do we form a strategy? I’m unsure of the most efficient way to keep track of the correct digits, and how to get back on track if a yellow LED switches to red. I am also unsure of how this affects the equation for the expectation. Could someone guide me on this please? Thank you!
Since nothing a priori is known, any first guess will work in the same way, we guess
Few cases are possible (we don't know what is the case, except for color),
$3$ to $5$ digits were guessed right. Then for every digit $d_1, \ldots, d_6$ try it(the digit) from $1$ to $9$, e.g. for $d_1$
if color changed (on the first try) to RED, we've initially guessed $3$ right digits, incl. $d_1=0$
if color change to GREEN (during those 9 trials), we are done
otherwise, inconclusive. Then proceed in the same way with other locations $d_2$ till $d_6$. If there were $3$ or $5$ correct digits initially, this will be established on those trials. We will need at worst all $54$ trials in case of $5$ (but we will learn the number), for $3$ after at most $28$ trials we will know it is $3$ and which digits are right (once you know it is $3$ - $1$ trial is enough to check every digit if it is right or not, still inside $28$).
after $1 + 54$ trials, we established, there are $4$ right digits in $0-0-0-0-0-0$ guess. Now, pick a pair of digits, e.g. $d_1$ and $d_2$, and change them to $1-1$ (if color changed to RED - those were right digits, if to GREEN - done). In $3$ trials you find $2$ right zeros, in other $3$ the other right pair. In $18$ trials you can find the right value of two missing digits (you turn off two right, and run from $1$ to $9$ independently)
in the same spirit you can establish in $27$ trials, all the digits, in case of $3$.
check out, that initial testing could be done the triplets of digits [did not think this case for optimality].
The more difficult is the case of RED light on $0-0-0-0-0-0$ trial.
in $1000$ trials, trying all the triplets of $d_1, d_2, d_3$, we can establish their true value, and from that point proceed like above [more $27$] - this is the upper bound on the number of trials
The coverage idea
is to try numbers, like in the kids game [have no idea of its English name]. Each number you try and get RED - you basically drop numbers, that would otherwise give you YELLOW or GREEN.
Example:
After we have tried $0-0-0-0-0-0$, we know that $n$ could not be $0, 1, 2, 10, 11, 999$, etc. In fact, any first try will eliminate $15850$ possibilities. Interestingly, guessing next $1-1-1-1-1-1$ will eliminate $15830$, etc. While, I'm yet to establish there are at most $100$ guesses, which eventually result in a YELLOW light.
UPDATE [31/07/2019]: (After I have optimized code enough, so it will be solvable in the short - order of hours amount of time)
As I have stated previously, $1,000$ consecutive trials of $3$ right-most digits will hit every possible number with $\bf{\color{orange}{\text{YELLOW}}}$ light eventually.
Therefore we are interested in anything that is faster. I have applied a greedy algorithm, that traverses all the numbers and picks the number, that covers (i.e. turns light yellow) the most yet uncovered numbers. It is not the optimal (i.e. probably the list could be made short, by choosing some other numbers, or just by changing the order of numbers in coverage could lead to over better numbers to pick).
In the abstract land, build a graph on $1000000$ vertices. Define edges between two vertices $v$ and $u$, if the Hamming distance between their decimal representation is at least $3$. We want to find a dominating set in this graph. Such that, if we complete the dominating set, so we can move from one vertex in it to another (weights are just a Hamming distance), some Hamiltonian path through it has a minimal weight.
Unfortunately, I'm not that good in complexity, so I suppose both DS and HPP are hard problems.
In my attempt I have found a $292$ big dominating set. And finally iterated few times through it to find some Hamiltonian path with eventual weight of $949$ (i.e. $949$ digit changes, before you deterministically hit $\bf{\color{orange}{\text{YELLOW}}}$ light on any possible number, but without paying for the first attempt). Recall that after the yellow light was produced, it still could require another $54$ attempts to establish which digits are right (and the value of which were guessed wrong).
Overall, this strategy requires $949$ digit changes to hit yellow light, then $54$ (plus maybe $6$ to set the guessed digit to the wrong state and back in the final attempt). This is $1007$ attempts instead of at most $1026 = 999 + 27$ in the trivial strategy approach
Let call it $2 \text{%}$-better strategy.
Therefore, slightly less than $1\$$ is a safe point.
Dump of the coverage (i.e. combinations should be tried in this order):