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. An argument in favor of my interpretation is that I can't just drop hints 4 and 5.
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