In this puzzle [1,2], we need to determine what the 3-digit passcode is, using a few hints. Each digit is an integer between 0 and 9. The hints are:
Let's see if we can shoehorn this into a MIP model.
Binary variables
It is tempting to use an integer variable for this: \[\color{darkred}y_i \in \{0,\dots,9\}, i \in{1,2,3}\] However, some constraints, like \(\color{darkred}y_i \ne 7\) are a bit difficult to handle (you need an extra binary variable for this). Often it is easier, for these types of problems, to use a binary variable: \[\color{darkred}x_{i,k} \in \{0,1\}, i \in \{1,2,3\}, k\in \{0,\dots,9\}\] Formally, \[\color{darkred}x_{i,k}=\begin{cases}1&\text{if digit \(i\) has value \(k\)} \\ 0 & \text{otherwise}\end{cases}\]Obviously, we need to add the constraint: \[\sum_k \color{darkred}x_{i,k}=1\] so a digit takes on exactly one value. Forbidding 7 is now a question of fixing \(\color{darkred}x_{i,7}=0\).
Constraints
Now let's work on the constraints. We translate each hint single-mindedly using only this hint. I.e., we don't share information between hints. That we leave to the solver.
- \(|6|8|2|\) One number is correct and well placed.
My interpretation is: exactly one number is correct and well placed. This means: \[\color{darkred}x_{1,6} +\color{darkred}x_{2,8}+\color{darkred}x_{3,2}=1\]
This is a good example where math is a more precise language than English. Formulating a mathematical model forces the modeler to fill in the gaps. Often, this is a good exercise to get a better understanding of the problem. - \(|6|1|4|\) One number is correct but wrongly placed.
I think this means: \[\color{darkred}x_{2,6}+\color{darkred}x_{3,6}+\color{darkred}x_{1,1}+\color{darkred}x_{3,1}+\color{darkred}x_{1,4}+\color{darkred}x_{2,4}=1.\] - \(|2|0|6|\) Two numbers are correct but wrongly placed.
Same treatment: \[\color{darkred}x_{2,2}+\color{darkred}x_{3,2}+\color{darkred}x_{1,0}+\color{darkred}x_{3,0}+\color{darkred}x_{1,6}+\color{darkred}x_{2,6}=2.\] - \(|7|3|8|\) Nothing is correct.
I interpret this as: \(\color{darkred}x_{i,7}=0\),\(\color{darkred}x_{i,3}=0\), and \(\color{darkred}x_{i,8}=0\). This can be done by fixing variables. We can also write this as a single constraint: \[\sum_i \left(\color{darkred}x_{i,7}+\color{darkred}x_{i,3}+\color{darkred}x_{i,8}\right)=0.\] Even more aggressive: we could have removed 3,7,8 from the domain of index \(k\), i.e., \(k \in \{0,1,2,4,5,6,9\}.\) Whatever you choose to express this, the presolver will ultimately remove these variables from the model. - \(|7|8|0|\) One number is correct but wrongly placed.
\[\color{darkred}x_{2,7}+\color{darkred}x_{3,7}+\color{darkred}x_{1,8}+\color{darkred}x_{3,8}+\color{darkred}x_{1,0}+\color{darkred}x_{2,0} = 1\]
This is a feasibility problem: to make it a MIP model, we just introduce a dummy objective.
Unique solution
The result is:
---- 81 VARIABLE x.L 0 2 4 i1 1.000 i2 1.000 i3 1.000
I.e., our solution is \(|0|4|2|\).
Looking carefully at the solver log, we see:
Tried aggregator 2 times.MIP Presolve eliminated 4 rows and 27 columns.Aggregator did 4 substitutions.All rows and columns eliminated.Presolve time = 0.00 sec. (0.04 ticks)
Proven optimal solutionMIP Solution: 0.000000 (0 iterations, 0 nodes)
A well-formed puzzle has a single, unique solution. We can check this is the case by adding the constraint: \[\color{darkred}x_{1,0}+\color{darkred}x_{2,4}+\color{darkred}x_{3,2}\le 2\] If we solve this, we should see: infeasible. That is indeed the case.
--- MIP status (103): integer infeasible.
So there is exactly one solution.
Debunking claims
hints 4 and 5 are not needed, you can do it all from 1, 2 and 3
From hint 1 and 2 we can see that 6 isn’t part of the solution.
I think they interpret Hint 2 as:
\(|6|1|4|\) One number is correct but wrongly placed. And no number is correct and correctly placed.
I don't add the second part. I assume that hint 2 does not say anything about correctly placed numbers.
Here we see how a seemingly good description is not as watertight as a proper mathematical problem statement.
Arguments in favor of my interpretation are that I use all hints, and that the solution is unique.
Conclusions
Developing a formal mathematical model is very different from solving the riddle by hand. The focus is more on precision and correctness. We don't take shortcuts to quickly deduce something.
We worked on formulating one hint at a time. The simultaneous-equations aspect of the model is handled by the solver. When doing things by hand, we try to combine hints as quickly as possible to make deductions.
Proving uniqueness is also very different. When manually solving the riddle, we want to ensure there are no "branches" in our logic. Here, we use a no-good constraint to forbid the solution.
GAMS Model
$onText
Find
|x1|x2|x3| where x(i) ∈ {0,..,9}
with the following rules
|6|8|2| One number is correct and well placed
|6|1|4| One number is correct but wrongly placed
|2|0|6| Two numbers are correct but wrongly placed
|7|3|8| Nothing is correct
|7|8|0| One number is correct but wrongly placed
References:
https://www.reddit.com/r/mathmemes/comments/1bbld8t/okay_reddit_geniuses_what_is_the_answer_im_stuck/
https://www.youtube.com/watch?v=lK857tIT4X4
---------------------------------------------------------------
|6|8|2| One number is correct and well placed
<=> x[1,6]+x[2,8]+x[3,2]=1
|6|1|4| One number is correct but wrongly placed
<=> x[2,6]+x[3,6]+x[1,1]+x[3,1]+x[1,4]+x[2,4]=1
|2|0|6| Two numbers are correct but wrongly placed
<=> x[2,2]+x[3,2]+x[1,0]+x[3,0]+x[1,6]+x[2,6]=2
|7|3|8| Nothing is correct
<=> x[1,7]+x[2,7]+x[3,7]+x[1,3]+x[2,3]+x[3,3]+x[1,8]+x[2,8]+x[3,8]=0
|7|8|0| One number is correct but wrongly placed
<=> x[2,7]+x[3,7]+x[1,8]+x[3,8]+x[1,0]+x[2,0]=1
$offText
*-----------------------------------------------------------------------
* base model
*-----------------------------------------------------------------------
Sets
i 'position' /i1,i2,i3/
v 'value' /0*9/
;
binary variable x(i,v);
equations
onevalue(i) 'each position has one value'
e1 '|6|8|2| One number is correct and well placed'
e2 '|6|1|4| One number is correct but wrongly placed'
e3 '|2|0|6| Two numbers are correct but wrongly placed'
e4 '|7|3|8| Nothing is correct'
e5 '|7|8|0| One number is correct but wrongly placed'
;
onevalue(i).. sum(v, x(i,v)) =e= 1;
e1.. x['i1','6']+x['i2','8']+x['i3','2'] =e= 1;
e2.. x['i2','6']+x['i3','6']+x['i1','1']+x['i3','1']+x['i1','4']+x['i2','4'] =e= 1;
e3.. x['i2','2']+x['i3','2']+x['i1','0']+x['i3','0']+x['i1','6']+x['i2','6'] =e= 2;
e4.. sum(i,x[i,'7']+x[i,'3']+x[i,'8']) =e= 0;
e5.. x['i2','7']+x['i3','7']+x['i1','8']+x['i3','8']+x['i1','0']+x['i2','0'] =e= 1;
variable z;
equation obj 'dummy';
obj.. z=e=0;
* model 1: solve problem as is
model m1 /all/;
solve m1 minimizing z using mip;
display x.l;
* result:
* |0|4|2|
*-----------------------------------------------------------------------
* check solution is unique
* this model should be infeasible
*-----------------------------------------------------------------------
* model m2: forbid this solution (from m1)
* now should be infeasible
equation forbid 'cut off solution';
forbid.. sum((i,v)$(x.l[i,v]>0.5),x[i,v]) =l= 2;
model m2/m1+forbid/;
solve m2 minimizing z using mip;
abort$(m2.modelstat = %modelStat.optimal% or m2.modelstat = %modelStat.integerSolution%) "This should be infeasible;";
* result:
* (integer) infeasible
*-----------------------------------------------------------------------
* can we find the same solution using just equations 1,2,3?
* this will give a wrong solution
*-----------------------------------------------------------------------
model m3 /m1-e4-e5/;
solve m3 minimizing z using mip;
display x.l;
* result (depending on solver):
* |6|6|3|
References
- Okay reddit geniuses, what is the answer? I’m stuck…., https://www.reddit.com/r/mathmemes/comments/1bbld8t/okay_reddit_geniuses_what_is_the_answer_im_stuck/
- Crack the passcode! I'm stuck... Reddit crack the password puzzle r/mathmemes, https://www.youtube.com/watch?v=lK857tIT4X4
No comments:
Post a Comment