# Rendezvous on the Line with Different Speeds and Markers That Can Be Dropped at Chosen Time
## 4 Solution of the Problem without Marker  
The optimal strategies of the problem without marker are given in Corollary 1. There are eight unknowns \(v_{i}\) and \(d_{i}\), the rendezvous time being a consequence of these variables. To reduce the problem to a family of linear programs we rewrite the strategies to remove the products \(v_{i}\cdot t\) by introducing new variables \(vt_{i}\) with the bounds \(0\leq vt_{i}\leq v\cdot(t_{i}-t_{i-1})\), where \(v\) is the maximal speed of player I. To take into account that the speed of player I may be negative (when player I is going backward), we introduce new variables \(a_{i}=\pm 1\) and the motion is computed relatively to \(a_{i}\cdot vt_{i}\). Notice that \(a_{i}\) is a parameter that is fixed before calling the LP-solver (hence, the problem is still linear). To define the meeting times \(t_{i}\), we need to specify in which order they occur. Ordering the meeting times amounts to choosing a permutation \(\sigma\) of \(\{1,2,3,4\}\) such that \(t_{i}=t^{\sigma(i)}\) where \(t^{i}\) are defined by Equations (2)-(5). For this, we introduce new variables \((o_{i},b_{i})\) with \(o_{i}=\pm 1\) and \(b_{1}=\pm 1\) to refer to specific agents of player II. Concretely,  
* Agent 1 is referred by \((o_{i}=+1,b_{i}=+1)\) and the rendezvous time \(t^{1}\) is defined by (2),
* Agent 2 is referred by \((o_{i}=+1,b_{i}=-1)\) and the rendezvous time \(t^{2}\) is defined by (3),
* Agent 3 is referred by \((o_{i}=-1,b_{i}=+1)\) and the rendezvous time \(t^{3}\) is defined by (4),
* Agent 4 is referred by \((o_{i}=-1,b_{i}=-1)\) and the rendezvous time \(t^{4}\) is defined by (5). The rendezvous always occur in the order \((o_{1},b_{1})\), \((o_{2},b_{2})\), \((o_{3},b_{3})\), \((o_{4},b_{4})\). The values of \(o_{i}\) and \(b_{i}\) are given by:  
\[\min_{\Lambda_{i}}\;t_{1}+t_{2}+t_{3}+t_{4}\] \[o_{1}+d_{1}b_{1}t_{1}=a_{1}vt_{1}\] \[o_{2}+d_{1}b_{2}t_{1}+d_{2}b_{2}(t_{2}-t_{1})=a_{1}vt_{1}+a_{2}vt _{2}\] \[o_{3}+d_{1}b_{3}t_{1}+d_{2}b_{3}(t_{2}-t_{1})+d_{3}b_{3}(t_{3}-t _{2})=a_{1}vt_{1}+a_{2}vt_{2}+a_{3}vt_{3}\] \[o_{4}+d_{1}b_{4}t_{1}+d_{2}b_{4}(t_{2}-t_{1})+d_{3}b_{4}(t_{3}-t _{2})+d_{4}b_{4}(t_{4}-t_{3})=a_{1}vt_{1}+\] \[a_{2}vt_{2}+a_{3}vt_{3}+a_{4}vt_{4}\] \[0\leq vt_{1}\leq v\cdot t_{1}\] \[0\leq vt_{2}\leq v\cdot(t_{2}-t_{1})\] \[0\leq vt_{3}\leq v\cdot(t_{3}-t_{2})\] \[0\leq vt_{4}\leq v\cdot(t_{4}-t_{3})\]  
\[o_{1}+d_{1}b_{1}t_{1}=a_{1}vt_{1}\]0 \[o_{1}+d_{1}b_{1}t_{1}=a_{1}vt_{1}\]1  
For the computation of the solution, we use the variables \(o_{i},b_{i},d_{i},a_{i}\) as parameters. For each set of values, we solve the corresponding linear program. The number of linear programs solved was 1536, which was solved in a few seconds using the Python Gurobi library [40]. Notice that by symmetry, we fixed \(a_{1}=1\) and \(d_{1}=1\). The plot of the results are shown in Figure 2, where the optimal rendezvous value is plotted versus the maximal speed of player I for discrete values \(n/1000\), \(n=0,1,\ldots,1000\). Besides the computation of the optimal rendezvous values, we recorded the corresponding optimal strategy. We observe that for \(v\leq 0.618\) the optimal strategy is (\(a_{1}=0\), \(a_{2}=0\), \(a_{3}=1\) and \(a_{4}=-1\)) for player I and (\(d_{1}=1,\;d_{2}=1,\;d_{3}=-1,\;d_{4}=-1\)) for player II as illustrated in \[o_{1}+d_{1}b_{1}t_{1}=a_{1}vt_{1}\]2 In terms of the optimal strategy of Corollary 1, the speeds of player I are \(v_{1}=0\), \(v_{2}=0\), \(v_{3}=-v\) and \(v_{4}=v\). Notice that player I can play the symmetric strategy \((a_{1}=0,\;a_{2}=0,\;a_{3}=1,\;a_{4}=-1)\) as well, which is not illustrated. It is relevant to observe that until \(t^{2}=t^{3}\) the wait-for-mummy strategy is the optimal strategy for player I, as motion starts only after.