6
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Assuming, of course, that $p,q$ are coprime... $\endgroup$ Jul 1, 2017 at 20:21
  • $\begingroup$ 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$. $\endgroup$
    – user451844
    Jul 1, 2017 at 20:45
  • $\begingroup$ @RoddyMacPhee: but the first has only run four minutes when you turn it the second time, so it only takes four minutes to empty $\endgroup$ Jul 1, 2017 at 21:00
  • $\begingroup$ Sorry reading problem apparently. It's still a Frobenius like problem I think, with the set $\{4,9,13\}$ $\endgroup$
    – user451844
    Jul 1, 2017 at 21:08
  • $\begingroup$ @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. $\endgroup$ Jul 1, 2017 at 21:25

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 47=17+17+13; 46=23+23;45=9+9+9+9+9;44= ? ;43=17+17+9;42= listed; $\endgroup$
    – user451844
    Jul 2, 2017 at 2:33
  • $\begingroup$ 44=9+9+13+13, 41=13+28, 40=9+9+9+13, 39=13+13+13, 38=? $\endgroup$
    – nickgard
    Jul 2, 2017 at 11:45
  • $\begingroup$ 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) $\endgroup$
    – user451844
    Jul 2, 2017 at 12:38
  • $\begingroup$ okay checked again it was 38 as the highest it couldn't find at least into the 700's + $\endgroup$
    – user451844
    Jul 2, 2017 at 13:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .