Tweeted twitter.com/StackMma/status/1014759976391335936 occurred Jul 5 '18 at 6:36 4 added 212 characters in body edited Jul 5 '18 at 2:20 David G. Stork 26.2k22 gold badges2323 silver badges5959 bronze badges 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 edited Jul 5 '18 at 1:03 David G. Stork 26.2k22 gold badges2323 silver badges5959 bronze badges 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 edited Jul 5 '18 at 0:06 David G. Stork 26.2k22 gold badges2323 silver badges5959 bronze badges 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 asked Jul 5 '18 at 0:00 David G. Stork 26.2k22 gold badges2323 silver badges5959 bronze badges