How much are you willing to pay for this treasure chest game? 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!
 A: This answer is limited to the first part of the problem, because there seems to be an error in the OP's approach there.
The OP's answer, $x\lt1000/10^6$ is correct only if there is a single attempt at unlocking the chest, or if by "willing to pay" what's meant is "willing to pay with no risk whatsoever of losing money."  If "willing to pay" has its more typical meaning of "willing to risk in order to get a positive expected return," and if you have unlimited attempts (and if you can keep track of the all those attempts, so you don't try the same combination twice), then the correct answer is $x\lt2000/10^6$ (or $1000/500{,}000$).  
That is, if you systematically explore all $10^6=1{,}000{,}000$ different combinations without ever repeating yourself (which is possible to do while changing just one digit at a time), it'll take, on average, $500{,}000$ attempts to find the combination that unlocks the chest, so the expected return is $E=1000-500{,}000x$, and this is positive if $x\lt1000/500{,}000=\$0.002$ (i.e., two-tenths of a penny per attempt).
A: (Only second part of the question. The first part seems trivial)
Short summary: it seems that a naive approach can find the combination in 200 tries (on average).
This problem can be thought of as a variant as the classic "bulls and cows" game, with the added restriction that a guess can differ by only one digit from the previous guess.
The optimal strategy is not obvious, but here is an observation and results from computer simulations.
Observation 1: after the LED turns yellow for the first time, you know one position for certain (the last one changed), and you can get the other two by turning the other five positions once or twice. If, after changing a digit, the LED stays yellow you keep the change. If it goes red you know the number for that position and you change it back. After determining those 3 change one of them to turn the led to red, and using at most 30 tries you can determine the values of the other 3.
Every time you make a change and the LED stays red you gain some information.  For example, if you try 1,2,3,4,5,6 and get red, 1,2,3,X,X,X is not possible, 1,2,X,4,X,X not possible, etc. At most you eliminate $15850 = 20 \cdot 9^3 + 15 \cdot 9^2 + 6 \cdot 9 + 1$ (first try, for instance), but in general some combinations might be rules out already, and in practice you eliminate 4,000 to 6,000 combinations in the first 50 moves or so.
I wrote some code which picks a guess by keeping track of all valid remaining combinations, picks a position in one valid combination which is different than the guess and changes the guess to match this value. This is obviously not optimal but can give an idea about the upper limits. It seems that this method can fine the combination in around 200 moves (on average). 
The code is not fast, so I run only 20-30 times, but I think somewhere between 150 and 250 (for the average) is reasonable.
Finding a better strategy seems interesting but not trivial.
