6

It is easy to show that if you can only earn $p$ or $q$ coins, with $p$ and $q$ coprimes, the largest number of coins which cannot be earned is $pq-p-q$.

If we have two hourglasses that last $p$ and $q$ minutes respectively, the longest number of minutes which cannot be measured is smaller: for example, if they last 9 and 13 minutes it is possible to measure 17 minutes by starting them together, turning the first one when it's empty, and turning it again when the second one is empty. When the first hourglass becomes empty again, 17 minutes are elapsed.

Is there a formula which gives the longest number of minutes which cannot be measured?

mau
  • 9,774
  • Assuming, of course, that $p,q$ are coprime... – Mark Fischler Jul 01 '17 at 20:21
  • Really? First, this sounds like a Frobenius number problem. Secondly, 9 minutes go by by the first time the first one is empty four minutes go by for the second to empty then 9 minutes go by for the first to empty again $9+4+9=22 \ne 17$. –  Jul 01 '17 at 20:45
  • @RoddyMacPhee: but the first has only run four minutes when you turn it the second time, so it only takes four minutes to empty – Ross Millikan Jul 01 '17 at 21:00
  • Sorry reading problem apparently. It's still a Frobenius like problem I think, with the set ${4,9,13}$ –  Jul 01 '17 at 21:08
  • @RoddyMacPhee: It is not quite that simple because you can't use as many $4$s as you like. You have to use a $13$ for every $4$, so it would be ${9,13,17}$ but you can also get $28$ by running three $9$s and two $13$s in parallel, having $1$ in the $13$ when the third $9$ finishes. Even the three number Frobenius problem has no simple solution. – Ross Millikan Jul 01 '17 at 21:25
  • Okay but it's a start it also also allows you to measure 9a+13b+17c=z which is the classical Frobenius number ( okay coin problem technically) problem. The question then, is what else you can do, to get numbers lower than the usual maximum. –  Jul 01 '17 at 21:32

1 Answers1

1

If you start the two hourglasses together, run $p$ through $k$ cycles, and turn over $q$ when the $k^{\text{th}}$ cycle of $p$ is done, you get $kp+(kp \bmod q)$ Similarly you can get $kq+(kq \bmod p)$. You can view it as a Frobenius problem with a larger set of numbers available. In your example, we have the following added numbers $$\begin {array} {r|r|r} k&p&q\\ \hline 1&-&17\\2&23&34\\3&28&42 \end {array}$$ You have the Frobenius problem with $\{9,13,17,23,28,42\}$ and my hand calculations show the largest nonrepresentable number to be $47$, improved by Roddy MacPhee to $38$. The Frobenius problem does not have a known solution for more than two sizes of coin.

Ross Millikan
  • 374,822
  • 47=17+17+13; 46=23+23;45=9+9+9+9+9;44= ? ;43=17+17+9;42= listed; –  Jul 02 '17 at 02:33
  • 44=9+9+13+13, 41=13+28, 40=9+9+9+13, 39=13+13+13, 38=? – nickgard Jul 02 '17 at 11:45
  • you could try it for any pair of two lowering the limit each time:

    using :

    my(a=[9,13,17,23,28,42],c=[]);for(x=1,#a,for(y=1,#a,for(z=0,20,for(b=0,20,c=concat(c,za[x]+ba[y])))));c=vecsort(c,,8) in PARI/GP, I get a upper limit of 29 (at least without the gaps from not going higher up in the multiples etc, okay it seems to be taking out the asterisk used for times in PARI/GP)

     –  Jul 02 '17 at 12:38
  • okay checked again it was 38 as the highest it couldn't find at least into the 700's + –  Jul 02 '17 at 13:41