From [1]:
The hour, minute and second hands of this clock are all the same length and move smoothly in a circle. The dial contains hour and minute markers, but the numbers are missing. Therefore, it’s impossible to tell which one of the 12 hour markers belongs to the 12. The two hands on the left are positioned exactly on hour markers, and the hand on the right is positioned between a minute and an hour marker. What time does the clock show?
It is possible to solve this without really any math, but, of course, here I try to model this as a mathematical programming model.
I denote the three hands as \(h_1\), \(h_2\), and \(h_3\). The hand \(h_1\) is the left lower one, \(h_2\) the left upper one, and \(h_3\) the hand on the right. Let's get the relative positions of these hands. We can read from the clock figure:
| hand | relative position |
|---|---|
| \(h_1\) | \(0\) |
| \(h_2\) | \(2\) |
| \(h_3\) | somewhere inside \((6.8,7)\) |
Notes:
- The symbol \(\mathit{\color{darkred}{relpos}}\) is really a parameter (data), but as I am not exactly sure about \(h_3\), I introduced a feasible interval for that one. The consequence is that this becomes a variable.
- A clock gives rise to modular arithmetic. We have 10:00 + 3 hours = 1:00.
- We can't have a mod operator in a standard mathematical programming model. So the first equation is written as: \[\begin{align}& \mathit{\color{darkred}{hpos}}_{h} = \mathit{\color{darkred}{relpos}}_{h} + \mathit{\color{darkred}{offset}} - 12\color{darkred}\delta_h \\ & \color{darkred}\delta_h \in \{0,1\}\end{align}\]
- We can't really do \(\mathit{\color{darkred}{relpos}}_{h3} \in (6.8,7)\) so we settle for \(\mathit{\color{darkred}{relpos}}_{h3} \in [6.8,7]\).
- The domain of \(\mathit{\color{darkred}{hpos}}_{h}\) is \([0, 11.999]\) to prevent ambiguity at 0 vs 12. There is no hard rule for choosing the tolerance. Too small, and feasibility tolerances in the solver render it useless. Too large: a big hole may make the model infeasible. My choice seems reasonable.
The next task is to model the assignment of hands to their role: indicating hours, minutes and seconds. To form a unique assignment of hands to roles, we can use a fragment of an assignment model: \[\begin{align} &\sum_h \mathit{\color{darkred}{assign}}_{h,r} = 1 && \forall r\\ & \sum_r \mathit{\color{darkred}{assign}}_{h,r} = 1 && \forall h \\ & \mathit{\color{darkred}{assign}}_{h,r} \in \{0,1\}\end{align}\] This gives us a mapping between hands and roles. Feasible levels for this can look like:
---- 86 VARIABLE assign.L assign unique role to hand hour minute second h1 1.000 h2 1.000 h3 1.000
Now we can move from \(\mathit{\color{darkred}{hpos}}_{h}\) to something like \(\mathit{\color{darkred}{rpos}}_{r}\) as follows: \[\mathit{\color{darkred}{rpos}}_{r} = \sum_h \mathit{\color{darkred}{assign}}_{h,r} \cdot \mathit{\color{darkred}{hpos}}_{h}\] Applying this we can see something like:
---- 87 VARIABLE hpos.L final position of hands (relpos + offset mod 12, in decimal hours) h1 10.000, h3 4.833 ---- 87 VARIABLE assign.L assign unique role to hand hour minute second h1 1.000 h2 1.000 h3 1.000 ---- 87 VARIABLE rpos.L position of hr/min/sec hand ∈[0,11.99] hour 4.833, minute 10.000
Note that hand \(h_2\) corresponding to seconds is at position zero (zeros are not printed here).
There is a slight issue here. As we multiply two variables, this formulation would make the model a nonconvex MIQCP (Mixed-Integer Quadratically Constrained). However, we can try a linearization. The idea is that we can linearize the product between a binary variable and a (bounded) continuous variable. I.e. consider \(\color{darkred}z = \color{darkred}\delta\cdot \color{darkred}x\) with \(\color{darkred}\delta \in \{0,1\}\) (binary) and \(\color{darkred}x \in [0,\color{darkblue}U]\) (continuous), then: \[\boxed{\begin{aligned} &\color{darkred}z = \color{darkred}\delta\cdot \color{darkred}x\\ & \color{darkred}\delta \in \{0,1\}\\& \color{darkred}x \in [0,\color{darkblue}U] \end{aligned}} \iff \boxed{\begin{aligned} & \color{darkred}z \le \color{darkblue}U \cdot \color{darkred}\delta \\& \color{darkred}z \le \color{darkred}x \\ & \color{darkred}z \ge \color{darkred}x - \color{darkblue}U\cdot (1-\color{darkred}\delta)\\ & \color{darkred}z \in [0,\color{darkblue}U]\\ & \color{darkred}\delta \in \{0,1\}\\& \color{darkred}x \in [0,\color{darkblue}U] \end{aligned}}\] The formulation on the right is completely linear. You can verify the correctness of this by substituting \(\color{darkred}\delta=0\) and \(\color{darkred}\delta=1\). Here is a good example where MINLP formulations can lead to more compact models.
We don't have an objective: this is a feasibility problem.
With this, we have solved the problem. We may add some reporting constraints to calculate the hours \(\in \{0,1,\dots,11\}\), minutes \(\in \{0,1,\dots,59\}\) and seconds \(\in \{0,1,\dots,59\}\) from our \(\mathit{\color{darkred}{rpos}}_{r}\) variable. The variable \(\mathit{\color{darkred}{rpos}}\) had a bit of a strange unit: position in terms of "hours" (i.e. 1/12th of a rotation). That made it a bit difficult to interpret. The new reporting variables are easier:
---- 95 VARIABLE v.L (integer) value in hours,minutes and seconds hour 4.000, minute 50.000
so our time would be 4:50.
Although this is actually more work than directly solving the problem by hand, it is still useful. We have discussed several interesting modeling issues (modular arithmetic, linearization of a product). And also, developing a model forces you to have a look at the problem a bit differently, and a bit more precisely. Sometimes, a model is not that important, but the modeling process is still a good way to gain a better understanding of the problem.
GAMS Models (nonlinear and linear)
$onText
Clock problem
see:
https://www.scientificamerican.com/game/math-puzzle-find-the-time/
$offText
Set
h 'hand' /h1,h2,h3/
r 'role' /hour,minute,second/
;
alias (h,hh);
variable
* hands h1,h2,h3
relpos(h) 'relative position of hands (define h1=0)'
offset 'from relpos'
hpos(h) 'final position of hands (relpos + offset mod 12, in decimal hours)'
modulo(h) 'binary variable to implement mod 12'
* role hour,minute,second
assign(h,r) 'assign unique role to hand'
rpos(r) 'position of hr/min/sec hand ∈[0,11.99]'
* reporting
v(r) '(integer) value in hours,minutes and seconds'
* objective
z 'dummy objective variable'
;
integer variable offset,v;
binary variable modulo, assign;
offset.up = 11;
hpos.lo(h) = 0;
hpos.up(h) = 11.999;
v.lo(r) = 0;
v.up(r) = 59;
v.up('hour') = 11;
* read relative positions from the clock:
* h1 = 0, h2 = 2, h3 ∈ [6.8,7]
table relposdata(h,*) 'relative position (interval) in units of hours (define h1=0)'
lo up
h1 0 0
h2 2 2
h3 6.8 7
;
relpos.lo(h) = relposdata(h,'lo');
relpos.up(h) = relposdata(h,'up');
equations
obj 'dummy objective'
e_hpos(h) 'position of hands (in decimal hours)'
e_assign1 'unique assignment hand <=> role'
e_assign2 'unique assignment hand <=> role'
assignpos 'calc rpos from hpos (nonlinear)'
* unit conversions
seconds 'calc seconds from rpos'
minutes 'calc minutes from rpos'
hours 'calc hours from rpos'
;
* label(h) = (relpos(h) + offset) mod 12
e_hpos(h).. hpos(h) =e= relpos(h) + offset - modulo(h)*12;
* unique assignment hand <=> role
e_assign1(r).. sum(h,assign(h,r)) =e= 1;
e_assign2(h).. sum(r,assign(h,r)) =e= 1;
assignpos(r).. rpos(r) =e= sum(h, assign(h,r)*hpos(h));
seconds.. v('second') =e= rpos('second')*60/12;
minutes.. v('minute') =e= rpos('minute')*60/12 - v('second')/60;
hours.. v('hour') =e= rpos('hour') - v('minute')/60 - v('second')/60/60;
obj.. z =e= 0;
*------------------------------------------------
* nonconvex quadratic model
*------------------------------------------------
model m1 /all/;
option miqcp=baron;
solve m1 minimizing z using miqcp;
display relpos.l,offset.l,hpos.l,assign.l,rpos.l,v.l;
*------------------------------------------------
* linearized model
*------------------------------------------------
positive variables prd(h,r) 'product prd(h,r)=assign(h,r)*hpos(h)';
prd.up(h,r) = hpos.up(h);
equations
prod1(h,r) 'linearization of product'
prod2(h,r) 'linearization of product'
prod3(h,r) 'linearization of product'
assignpos2(r) 'linearization of product'
;
prod1(h,r).. prd(h,r) =l= hpos.up(h)*assign(h,r);
prod2(h,r).. prd(h,r) =l= hpos(h);
prod3(h,r).. prd(h,r) =g= hpos(h)-hpos.up(h)*(1-assign(h,r));
assignpos2(r).. rpos(r) =e= sum(h, prd(h,r));
model m2 /m1-assignpos,prod1,prod2,prod3,assignpos2/;
solve m2 minimizing z using mip;
display relpos.l,offset.l,hpos.l,assign.l,rpos.l,v.l;
References
- Math Puzzle: Find the Time, https://www.scientificamerican.com/game/math-puzzle-find-the-time/
