12
$\begingroup$

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!

$\endgroup$
3
  • 2
    $\begingroup$ How do you arrive at your equations? For example, where does $6!$ come from? Assuming there are 10 choices per digit, the number of possible codes is $10^6$. $\endgroup$
    – Michael
    Jul 14 '19 at 3:20
  • $\begingroup$ @Michael oh silly me; will edit shortly! $\endgroup$
    – user107224
    Jul 14 '19 at 7:59
  • $\begingroup$ math.stackexchange.com/questions/1383971/… , One of the solutions is mine using Markov Chain method. $\endgroup$ Jul 15 '19 at 6:47
1
$\begingroup$
  • $\bf{\color{red}{\text{RED}}}$ is $0, 1, 2$ right digits
  • $\bf{\color{orange}{\text{YELLOW}}}$ is for $3, 4, 5$ right digits
  • $\bf{\color{green}{\text{GREEN}}}$ for the number itself
  • $n = \overline{d_6d_5d_4d_3d_2d_1}$

Since nothing a priori is known, any first guess will work in the same way, we guess

$0-0-0-0-0-0$

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$

    $0-0-0-0-0-1$ to $0-0-0-0-0-9$ are tried

    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):

231750

139790

159430

279637

257639

207536

923536

327580

370540

350948

351989

315189

815185

875104

951304

658394

738393

794593

595793

513593

413592

493997

491507

497605

293625

983655

981607

481403

441633

540634

520544

592542

256542

258112

554192

550722

91222

11762

13661

702661

302666

666666

626612

706319

806368

405328

55928

935920

845020

575080

215084

219046

209743

273443

663423

847423

857063

853253

103254

168154

148138

697138

617208

636203

349003

379906

272908

973418

912818

112806

112029

132098

178498

178649

78241

48521

388621

318652

218359

888379

843377

893747

890716

460386

970381

790281

395271

309275

304195

104110

605810

800

0

3008

69758

69370

69402

709102

725192

720693

120604

121325

107821

967824

147974

167987

987

54687

854517

862509

62589

23189

283188

888888

888565

180575

286574

886501

456701

426051

150051

870052

430852

464872

452870

472150

410137

230167

241107

241859

240898

910853

110913

582913

502483

922481

722088

751078

321076

341396

145796

945648

995663

175563

674523

671029

786029

786095

228091

236491

262591

662694

162711

111111

291311

194302

994709

999999

829399

429914

439518

336514

346785

749285

948282

946172

956476

952266

928760

124768

594678

534777

508737

501836

31835

34055

964015

904094

904931

714901

734956

24946

444444

408344

408265

468425

560465

566169

640169

680968

600778

600479

105459

187259

186247

537217

571297

861290

867450

687451

689031

685046

625366

625847

225875

227405

538805

597004

752014

642017

932077

832427

316427

320927

360228

764238

765432

742332

987312

87992

377932

379862

99867

91464

30234

35679

839671

884680

284360

383490

344458

526358

97356

692955

606155

659345

12345

16930

876935

801942

818446

728419

363819

333333

365307

755857

555555

909557

806684

814264

514239

437249

337141

737748

777777

773724

783844

796540

798120

753106

523200

222222

274216

774836

76896

196883

477883

499184

419626

589126

519374

613770

917795

71715

85213

22173

268973

648906

638586

631782

133062

563041

543961

547610

473675

485769

382734

824831

654891

711568

961143

498037

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ With every incorrect try you gain some information, so your argument is incorrect. $\endgroup$
    – pepster
    Jul 19 '19 at 3:34
  • $\begingroup$ @pepster, I'm always willing, and sometimes even happy, to have a mistake pointed out, but I don't see one here. Could you please elaborate on what information is gained with each incorrect try in the setting for first part of the problem? (I totally agree that useful, nontrivial information is gained in the setting for the second part, as your answer lays out, but in the LEDless first part, the failure of one combination does not rule out anything but itself.) $\endgroup$ Jul 19 '19 at 11:03
  • $\begingroup$ See my answer below. Every unsuccessful try eliminates 15850 combinations: all combinations which would gave yellow or green. 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. Not every guess reduces the total by that much, since some combinations might be already eliminated. $\endgroup$
    – pepster
    Jul 19 '19 at 17:04
  • $\begingroup$ @pepster, as I tried to make clear, you are answering the second part of the OP's question, while I am only addressing the first part. There are no lights in the first part of the question, so all you learn on each attempt is that that particular combination does not unlock the chest. $\endgroup$ Jul 19 '19 at 18:37
0
$\begingroup$

(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.

$\endgroup$
4
  • $\begingroup$ Observation 1 is only valid, if you change 1 digit at a time, which on average requires around 500 guesses to hit yellow. $\endgroup$
    – dEmigOd
    Jul 19 '19 at 12:53
  • $\begingroup$ This is the problem as stated, i.e. you pay for every digit change. I have no idea where this 500 comes from. Like I said, 200 seems closer to the truth. $\endgroup$
    – pepster
    Jul 19 '19 at 16:50
  • $\begingroup$ Suppose the initial guess has no digit set right? How are you able to manage it in less than 500 guesses in expectation? $\endgroup$
    – dEmigOd
    Jul 20 '19 at 5:46
  • $\begingroup$ Edited my answer so the explanation might be clearer. $\endgroup$
    – pepster
    Jul 20 '19 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.