¿Qué tiempo se puede medir con dos relojes de arena?

Question

Es fácil demostrar que si se puede solo se ganan $p$ o $q$ monedas, con $p$ $q$ coprimes, el mayor número de monedas que no puede ser ganada es $pq-p-q$.

Si tenemos dos relojes de arena que duran $p$ $q$ minutos respectivamente, el mayor número de minutos que no puede ser medido es menor: por ejemplo, si el pasado 9 y 13 minutos es posible medir 17 minutos a partir de ellos, convirtiendo el primero cuando está vacía, y convertirlo de nuevo cuando el segundo está vacía. Cuando el primer reloj de arena se convierte de nuevo vacía, 17 minutos de tiempo transcurrido.

Hay una fórmula que da el número más grande de los minutos que no pueden ser medidos?

Answer 1

Si usted comienza a los dos relojes de arena juntos, ejecute $p$ a través de $k$ ciclos, y la vuelta a $q$ cuando el $k^{\text{th}}$ ciclo de $p$ se hace, consigue $kp+(kp \bmod q)$ del mismo modo, usted puede conseguir $kq+(kq \bmod p)$. Puedes verlo como un problema de Frobenius con un conjunto mayor de los números disponibles. En tu ejemplo, tenemos los siguientes números $$\begin {array} {r|r|r} k&p&q\\ \hline 1&-&17\\2&23&34\\3&28&42 \end {array}$$ Usted tiene el problema de Frobenius con $\{9,13,17,23,28,42\}$ y mi mano cálculos muestran el mayor nonrepresentable número de $47$, mejorado por Roddy MacPhee a $38$. El problema de Frobenius no tienen una solución para más de dos tamaños de moneda.