3
$\begingroup$

Let there be a code $(a_1, a_2, a_3, \dots, a_n)$; with each term a real number between $0$ and $1$.

Suppose there is a lock, with $n$ circular cogs. To unlock it, each cog must be set to the value of that term in the code. That is, the first cog must be spun round to $a_1$, the second cog to $a_2$, all the way to the $nth$ cog, which is to be spun to $a_n$.

Each cog is modulo $1$; that is, the position $0$ is the same as position $1$. When unlocking it, the cogs can be spun either forwards or backwards. For instance, to get from $0.9$ to $0.1$ requires spinning the cog $0.2$ units forward or $0.8$ units backward. Any number of adjacent cogs can be spun together.

Suppose the lock starts with each cog at position $0$. It is easy to calculate the minimum distance that the cogs must be spun to reach the code and unlock it.

For instance, if the code is $(0.3, 0.6)$ the optimal solution is to spin both cogs forward $0.3$, and then the second cog forwards by $0.3$ again, for a total distance of $0.6$. If the code were $(0.2, 0.9, 0.7)$ an optimal solution would be to spin the first and second cogs forward $0.2$, and then to spin the second and third cogs backwards $0.3$; for a total distance of $0.5$.

Now for the question: for a given n, what code will maximize this minimum distance? It is clear that when $n=2$, the maximising code will be $(1/3, 2/3)$ or $(2/3, 1/3)$; for a distance of $2/3$. When $n=3$, the maximum distance that I can achieve is $0.8$, with the code $(1/5, 4/5, 2/5)$. However, I haven't proved that this is the maximum. Can anyone find a better code? What about for $n>3$ ?

$\endgroup$
  • $\begingroup$ You get a higher cost for $(1/2,0,1/2)$. $\endgroup$ – Arthur Jan 12 '17 at 6:54
  • $\begingroup$ Ah, good point - don't know how I overlooked that. $\endgroup$ – Thomas Delaney Jan 12 '17 at 7:01
2
$\begingroup$

Hint: try to solve (what appears to be) a harder problem, and compute for every $x$ and $n$ the function $g(x,n)$ defined as the maximum cost you can force out of $n$ cogs, given that the first cog needs to be turned by exactly $x$ (with $0\leq x \leq 1$). E.g. $g(x,1)=min(x,1-x)$. Can you write $g(x,n)$ recursively, i.e. as a function of $g(y,n-1)$? Can you solve the recursion?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.