Symmetric rendezvous, discrete model: (upper half of the HDVZ conjecture)
OpenSymmetricRendezvousLine.discrete_symmetric_rendezvous_value_le_seventeen_quartersConjecture (upper half of Han–Du–Vera–Zuluaga). In the discrete model of the symmetric rendezvous problem on the line, the value is at most :
Here is the infimum of the expected meeting time over the mixed strategies all of whose paths are integer zigzags (paths starting at that move at full speed and change direction only at integer times), both players using the same with independent randomisations and independent fair-coin orientations, starting at distance (see the definition file). Equivalently: for every there is a single mixed strategy over integer zigzags which, used by both players, has expected meeting time at most .
Since trivially, this statement is the upper half of the conjecture (Han, Du, Vera and Zuluaga; Open Problem Garden). All known upper bounds on , including the best proved one , come from explicit symmetric strategies of this discrete form, and the conjectured value is the apparent limit of the values of such strategies as their horizon grows. This is an open problem.
Formalization Note Values live in ; is the extended-real literal . The infimum ranges over all mixed strategies supported on integer zigzags, not over a finite grid or horizon.
import Definitions.Def_SymmetricRendezvousLine_defs
namespace SymmetricRendezvousLine
theorem discrete_symmetric_rendezvous_value_le_seventeen_quarters :
discreteSymmetricRendezvousValue ≤ 17 / 4 := by sorry
end SymmetricRendezvousLine