How much are you willing to pay for this treasure chest game?

Solution 1:

• $\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