Tweeted twitter.com/StackMma/status/1014759976391335936
4 added 212 characters in body
source | link

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

An approach

Suppose the state at step $t$ is: {Va[t], Vb[t]}

Then the possible states at step $t+1$ are (where Va and Vb without index are the full volumes):

{0, Vb[t]}

{Va[t], 0}

{Va, Vb[t]}

{Va[t], Vb}

{Va[t]- (Vb - Vb[t]), Vb}

{Va, Vb[t] -(Vb - Va[t])}

Where the last two require conditions on whether they can be performed. One could then form a decision tree of possible outcomes and search for a path that leads to the target final condition. I don't see, though, how one would prove that a target volume could never be achieved.

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

An approach

Suppose the state at step $t$ is: {Va[t], Vb[t]}

Then the possible states at step $t+1$ are (where Va and Vb without index are the full volumes):

{0, Vb[t]}

{Va[t], 0}

{Va, Vb[t]}

{Va[t], Vb}

{Va[t]- (Vb - Vb[t]), Vb}

{Va, Vb[t] -(Vb - Va[t])}

Where the last two require conditions on whether they can be performed.

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

An approach

Suppose the state at step $t$ is: {Va[t], Vb[t]}

Then the possible states at step $t+1$ are (where Va and Vb without index are the full volumes):

{0, Vb[t]}

{Va[t], 0}

{Va, Vb[t]}

{Va[t], Vb}

{Va[t]- (Vb - Vb[t]), Vb}

{Va, Vb[t] -(Vb - Va[t])}

Where the last two require conditions on whether they can be performed. One could then form a decision tree of possible outcomes and search for a path that leads to the target final condition. I don't see, though, how one would prove that a target volume could never be achieved.

3 added 382 characters in body
source | link

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

An approach

Suppose the state at step $t$ is: {Va[t], Vb[t]}

Then the possible states at step $t+1$ are (where Va and Vb without index are the full volumes):

{0, Vb[t]}

{Va[t], 0}

{Va, Vb[t]}

{Va[t], Vb}

{Va[t]- (Vb - Vb[t]), Vb}

{Va, Vb[t] -(Vb - Va[t])}

Where the last two require conditions on whether they can be performed.

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

An approach

Suppose the state at step $t$ is: {Va[t], Vb[t]}

Then the possible states at step $t+1$ are (where Va and Vb without index are the full volumes):

{0, Vb[t]}

{Va[t], 0}

{Va, Vb[t]}

{Va[t], Vb}

{Va[t]- (Vb - Vb[t]), Vb}

{Va, Vb[t] -(Vb - Va[t])}

Where the last two require conditions on whether they can be performed.

2 added 10 characters in body
source | link

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

A classic class of math puzzles involves two irregular containers, $A$ and $B$, having known volumes $V_A$ and $V_B$ and an infinite source of water (from a spigot, say). You can

  • fill either container to its top from the spigot
  • pour the water from one container into the other to the receiver's top
  • pour all the water from one container into the other (if it can hold it)
  • pour out (discard) the entire contents of a container

(You cannot place a mark on any intermediate height/volume of water on either container.)

The goal is to obtain some exact target volume $V_t$ of water (in either container).

Example

Suppose $V_1 = 7$ and $V_2 = 5$ and the target is $V_t = 4$. In that case you'd perform the following:

$$ \begin{array}{cc} A & B \\ \hline 7 & 0 \\ 2 & 5 \\ 2 & 0 \\ 0 & 2 \\ 7 & 2 \\ 4 & 5 \\ {\bf 4} & {\bf 0} \end{array} $$

and end with four (liters) in container $A$.

Question

How would you write a search function in Mathematica given $V_A$, $V_B$ and $V_t$ that would compute the (minimal) sequence of steps to obtain $V_t$, or "prove" that $V_t$ could never be obtained?

Test the code on $V_A = 12$, $V_B = 9$ and $V_t = 8$.

1
source | link