An Hourglass Puzzle

Question

This puzzle follows from the well known sand timer puzzles: A Sand Timer Challenge http://www.crazyforcode.com/sand-timer-puzzle/
http://www.cut-the-knot.org/hg_solution.shtml

Warmup:
You are given a timer of 4 minutes, and a timer of 7 minutes. The time starts when the first timer is flipped. Is there a time for which all larger integer values of time can be measured? Prove why or why not.

Easy:
Same rules as above, but now your timers are 5 minutes and 8 minutes.

Medium:
Same rules as above, but now your timers are 6 minutes and 11 minutes.

Hard:
Same rules as above, but now your timers are $m$ minutes and $n$ minutes, where $m>n>0$ and $m,n \in\mathbb{Z}$. (Basically find a generalization. If you want to solve this first be my guest...)

EDIT:

If you couldn't understand what I was asking.
Let $T$ be the set of all times that can be timed using timers $m$ and $n$.
Find $s\in T:s-1\notin T,\forall x>s:x\in\mathbb{Z},x\in T$.

Answer 1

Taking a huge risk, but hey...

W/U:

Times in the form of $4n + 7m$ can be measured. As long as a number is large enough, you can add 2*4-7 = 1 if the 7-minute hourglass is to be used at least once to measure the previous time, or 3*7 - 5*4 = 1 if the 4-minute hourglass is to be used at least four times (for at least 20 mins!). At our most conservative guess, it's 27, but since values greater than 19 will either have an $m$ that's at least 1 or $n$ that's at least 5, 20 will do as as a slightly less-conservative one. Also, 7+(7-4) = 10 and 4*2 + 4*2 (mod 7) = 9 minutes can be measured. 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7 are reachable while 6 isn't, so $T$=6.

E:

If it's $5n + 8m$, it can be measured. As long as a number is large enough, you can add 5*5 - 3*8 = 1 if the 8-minute hourglass is to be used at least thrice to measure the previous time, or 2*8 - 3*5 = 1 if the 5-minute hourglass is to be used at least thrice. At our most conservative guess, the first $5n + 8m$ number whose $n$ and $m$ equal 3 (39) will do. However, 8+(8-5) = 11, mins can also be measured. 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18 are reachable while 17 isn't. 5*2 + 5*2 (mod 8) = 12 mins can also be measured, so that makes 17 also reachable. 16, 15 are measurable, and so is 14 (see the image in the comments section), 13, 12, 11 and 10. 9 isn't, so $T$=9.

M:

For $6n + 11m$, it can be measured. As long as a number is large enough, you can add 6*2 - 11*1 = 1 if the 11-minute hourglass is to be used at least once to measure the previous time, or 11*5 - 6*9 = 1 if the 6-minute hourglass is to be used at least nine times. At our most conservative guess, it's 54+11 = 65, but since values greater than 53 will either have an $m$ that's at least 1 or $n$ that's at least 9, 54 will do as a slightly less-conservative one. However, 11+(11-6) = 16 mins can also be measured. Then again, if we start out flipping any hourglass as soon as it empties, only 1 minute's worth of sand will remain in the upper half of the 6-min hourglass after 11 mins, while the other empties. To measure any time longer than that, we can also flip the bigger one, then flip both when the smaller one empties, then do it again when the bigger one does, and so on. 11 can be measured while 10 can't, so $T$=10.

H (incomplete):

As long as $n$ and $m$ are co-primes, $k$ and $j$ values to satisfy $nk$ ≡ 1 (mod $m$) and $mj$ ≡ 1 (mod $n$) can be found. In addition, $mx$ + $mx$ (mod $n$) and $ny$ + $ny$ (mod $m$) values can be used to measure time. Also, if there's some amount of sand left in only one of the hourglasses in the middle of a measurement, the time this sand corresponds to can be continuously added by flipping the other at the time, then flipping both whenever one empties, ... (rinse and repeat), making $mx$ + $rmx$ (mod $n$) if the latter without r is less than $m$ and $ny$ + $sny$ (mod $m$) if the latter without s is less than $n$ also measurable. That means the smaller one of the aforementioned $nk$ and $mj$ ($(n,m)max*[(n,m)min-1]$ at most) is enough for the conservative limit.

---

---

VERY LATE EDIT:

Just wrote a Java program to find the generalized solution:

package hourglass;

import java.util.ArrayList;
import java.util.List;

public class Unreachables {

public static void main(String[] args) {
    // x = n, y = m
int x = 7;
int y = 9;

int MaxUnreachable = 0;

int ConsLim1 = 0;
int ConsLim2 = 0;

int ub1 = 1;
int ub2 = 1;
int SecGen = 0;

List<Integer> FirstGenList = new ArrayList<Integer>();
List<Integer> SecGenList = new ArrayList<Integer>();
List<Integer> ReachablesList = new ArrayList<Integer>();

SecGenList.add(0);

 for (int i=0; i<y; i++) {
    if ((i*x)%y == 1) {
        ConsLim1 = i*x;
    }
    if ((i*y)%x == 1 && i<x) {
        ConsLim2 = i*y;
    }               
 }

 int LesserConsLim = Math.min(ConsLim1, ConsLim2);

int MaxXFac = LesserConsLim/x;
int MaxYFac = LesserConsLim/y;  

     ///////////////////////////////////////////////////////////
  for (int j=0; j<=MaxXFac; j++) {
    for (int k=0; k<=MaxYFac; k++) { 
        if (j*x + k*y < LesserConsLim) {
            FirstGenList.add(j*x + k*y);
        }
    }
  }

    ///////////////////////////////////////////////////////////
  for (int l=0; l<MaxXFac; l++) {
    int base = l*x;
    int r = (l*x)%y;

     if (r<x) {
      for (int m=0; m<ub1; m++) {
        SecGen = base + r*m;
        if (SecGen<LesserConsLim && SecGen > 0) {
            SecGenList.add(SecGen);
            ub1++;
        }
      }
     }              
   }

  ub2 = 1;
  for (int n=0; n<MaxYFac; n++) {
    int base = n*y;
    int t = (n*y)%x;

     if (t<y) {
      for (int o=0; o<ub2; o++) {
        SecGen = base + t*o;
        if (SecGen<LesserConsLim && SecGen > 0) {
            SecGenList.add(SecGen);
            ub2++;
        }
      }
     }              
   }

  for (int p=0; p<FirstGenList.size(); p++){
      for (int r=0; r<SecGenList.size(); r++){
          int PotRes = FirstGenList.get(p)+SecGenList.get(r);
           if (PotRes<LesserConsLim && ReachablesList.indexOf(PotRes)<0){
               ReachablesList.add(PotRes);  
           } 
      }
  }

  for (int z=LesserConsLim-1; z>0; z--){
      if (ReachablesList.indexOf(z)<0){
          MaxUnreachable = z;
          break;
          }       
      }


  System.out.println(MaxUnreachable); // our solution

    }
}

Answer 2

Not exactly the most precise answer but:

There is a theorem known as the Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) that states: if $m$ and $n$ are relatively prime, then for nonnegative integers $a,b$, the largest integer that cannot be expressed in the form $am + bn$ is $mn-m-n$.

However, note that for sand timer problems we can flip over a timer while the other is going. Thus we aren't restricted to nonnegative integers. So by using the CMT, we overestimate the minimum value, but we still get a value nonetheless.

So for the warmup:

Since $7$ and $4$ are relatively prime, we get: $28-7-4=17$. So we can definitely measure all times over $17$ min. Note that as others have computed already, you can measure all values over $6$ min.

Easy:

Since $5$ and $8$ are relatively prime, we get: $40-5-8 = 27$. So we can definitely measure all times over $27$ min.

Medium:

Since $6$ and $11$ are relatively prime, we get: $66-6-11 = 49$ So we can definitely measure all times over $49$ min.

Hard:

If $m$ and $n$ are relatively prime, then we know all numbers above $mn-m-n$ can be measured by the two timers.

Answer 3

In general, you can measure all combinations of the following times:

1. $n$
2. $m$
3. $2m - n$
4. $4n - m$
5. $3m - 2n$
6. $6n - 2m$

And times $t(x)=min(A \cdot m,B \cdot n) + (x \cdot \delta)$ where

$max(A \cdot m,B \cdot n)-min(A \cdot m,B \cdot n)=\delta$

---

Item 1 is found by starting timer $n$ and noting when expired.

Item 2 is found by starting timer $m$ and noting when expired.

Item 3 is found by starting timers $m$ and $n$ at the same time. When timer $n$ has expired reset $n$. When timer m has expired flip $n$. This gives you the time $2m - n$.

Item 4 is found by starting timers $m$ and $n$ at the same time. When timer $n$ has expired reset $n$. When timer $m$ has expired reset $m$. When timer $n$ has expired flip $m$. This gives you the time $4n - m$.

Item 5 is found by starting timers $m$ and $n$ at the same time. When timer $n$ has expired reset $n$. When timer $m$ has expired reset $m$ and flip $n$. When timer $n$ has expired flip $m$. This gives you the time $3m - 2n$.

Item 6 is found by starting timers $m$ and $n$ at the same time. When timer $n$ has expired reset $n$. When timer $m$ has expired reset $m$. When timer $n$ has expired reset $n$ and flip $m$. When timer $m$ has expired flip $n$. This gives you the time $6n - 2m$.

---

Warm-up $(7,4)$ $t=7$

Easy $(8,5)$ $t=10$

Medium $(11,6)$ $t=11$

Hard (In-progress)

In general we are looking for $a$,$b$,$c$,$d$,$e$,$f$ in

$t(a,b,c,d,e,f) = a(m)+b(n)+c(2m-n)+d(4n-m)+e(3m-2n)+f(6n-2m)$

such that $t$ is minimized according to the problem statement.

Answer 4

For all versions:

Start both timers. When either timer is empty, flip it.

Eventually, there will come a time when one timer is flipped 1 minute after the other one was flipped. At that point, flip both timers. 1 minute later, the other one will be empty; flip both again. From then on, every minute, one of the timers will be empty, and you flip both timers.

Warmup:

Flip the small one at 4, larger at 7, both at 8, both at 9, etc.

Every time from 7 minutes up can be measured.

Easy:

Flip small at 5, big at 8, small at 10, small at 15, both at 16, etc.

Every time from 15 minutes up can be measured.

Medium:

Flip small at 6, big at 11, both at 12, etc.

Every time from 11 up can be measured.

Hard:

Let $x=GCF(m,n)$. Follow the rules above, and eventually one of the timers will flip $x$ minutes after the other. From that time on, flip both timers whenever one is empty. Every multiple of $x$ from that point on will be measured.

Only gets all integer values if $m$ and $n$ are relatively prime.

Answer 5

21 min

When one of the hourglasses ends, we can return the same hour or the other hour. If we return the 11-minute hourglass after the 6-minute hourglass has expired twice (only 1 minute has passed) it will end in 13 minutes: 6x2 + (6x2-11) = 13.

If we turn back the 6-minute hourglass after the 11-minute hourglass ends (only 5 minutes have passed) it will end in 16 minutes: 11 + (11 - 6) = 16

We get numbers that are not multiples of 6 as the following combination: T = 6a+11b + (13c+16d)

• 6n, n≥1.
• 6n+1=6(n-2)+13, n≥2.
• 6n+2=6(n-4)+13×2, n≥4.
• 6n+3=6(n−4)+11+16, n≥4.
• 6n+4=6(n−2)+16, n≥2.
• 6n+5=6(n−1)+11, n≥1. The durations of 1, 2, 3, 4, 5, 7, 8, 9, 10, 14, 15, 20 and 21 minutes cannot be measured. Therefore, any integer greater than 21 minutes can be measured.