4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Do we have to find the exact limit, or will just proving if it's possible or not and if so, under what conditions do? $\endgroup$ – Nautilus Jul 24 '15 at 22:24
  • $\begingroup$ @Nautilus Yes you need to find it $\endgroup$ – qwertylpc Jul 24 '15 at 22:53
  • $\begingroup$ Just to confirm, in the "Warmup" scenario you cannot measure 3 minutes. Since even though you could flip both over and know that when the 4 minute timer ran out there are 3 minutes left in the 7 minute timer, the time starts when the first timer is flipped so it's already running. Correct? $\endgroup$ – Duncan Jul 24 '15 at 23:06
  • $\begingroup$ @Duncan Correct $\endgroup$ – qwertylpc Jul 24 '15 at 23:14
  • 1
    $\begingroup$ This is isomorphic to starting at one corner of an $m$ by $n$ rectangle, and repeatedly picking either an orthogonal or 45-degree diagonal direction and traveling in that direction until you hit a wall. $\endgroup$ – Lopsy Jul 26 '15 at 1:26
3
$\begingroup$

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

    }
}
$\endgroup$
  • $\begingroup$ I appreciate the effort, but your reasoning is off a bit. For example, 13 can be reached by: Flip 4. Wait 4 min and start the 4 and 7. After 4 min reset the 4. At the end of another 3 min (total of 11) reset the 7, at which point the 4 will have 1 min left. After that minute expires (a total of 12 min) the 7 will have 6 min left, so flip it so it has 1 minute left, bringing us to 13 minutes. $\endgroup$ – qwertylpc Jul 25 '15 at 1:29
  • $\begingroup$ Edited my post. $\endgroup$ – Nautilus Jul 25 '15 at 8:58
  • 1
    $\begingroup$ 14 can be measured in the second case. I don't want to illustrate how just yet..., but I'm sure you can figure it out. $\endgroup$ – qwertylpc Jul 26 '15 at 2:23
  • $\begingroup$ Whelp. So it can be measured this way? i.imgur.com/lSRMlFT.jpg $\endgroup$ – Nautilus Jul 26 '15 at 10:36
  • 1
    $\begingroup$ I don't see an issue besides the fact that it appears your H is incomplete. The other parts are correct $\endgroup$ – qwertylpc Jul 27 '15 at 19:56
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 7 is the correct answer for the warmup. However, 15 is not the correct answer for the second part. 14 can be achieved using a 5 and 8 minute timer. $\endgroup$ – qwertylpc Jul 26 '15 at 2:22
0
$\begingroup$

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.

$\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.