Abstract Algebra Bucket Problem
You are pouring water from a Faucet of Arbitrarily Large Output into an empty Tank of Arbitrarily Large Output into an empty Tank of Arbitrarily Large Capacity, and you have two containers with which to transfer this water, one holding 16 liters and the other holding 26 liters. You are allowed to fill either container from the Faucet and dump all of it into the Tank, and once there is enough water in the Tank, you are allowed to completely fill either container from the Tank and dump it into the Great Drain. Describe all possible numbers of liters of water you can put into the Tank, and prove your answer.
Question provided by Tim Hsu
Like in any other true engineering household, last night my dad referred me to this question, and the two of us spent maybe half an hour trying to find a good solution to it. Realize that he's taking this class as one of the last prereqs for getting into graduate school as a math major, and I just finished multidimensional calculus, so I won't be able to formally prove it to the rigor technically required.
We started shooting at the easiest targets. Every multiple of 16 and 26 are possible. These numbers can be expressed simply as 16⋅x and 26⋅y, with x and y being positive integers. You can also add some of one and some of the other, so really the numbers possible were more along the lines of 16⋅x + 26⋅y ≥ 0. Then considering that bucketfuls can also be removed from the Tank, you end up with 16⋅x + 26⋅y − (16⋅z + 26⋅w) ≥ 0, with z and w also positive integers.
The final solid progress we made was realizing that adding in a bucket, then removing it was pointless, so the formula can be simplified farther to be 16⋅x + 26⋅y ≥ 0, x and y only contrained to be integers. We also ended up making conjectures that we cannot make any odd number of liters in the tank, and my dad theorized that you'll reach some point when every even number is possible, taking the last conjecture into consideration (ie {every even number} ≥ n).
That's all well and good, but we haven't really said anything that can be proven mathematically. It wasn't until I was laying in my bed later that I really broke the question:
If at some point ≥ n all even numbers are possible, what's keeping us from just taking some number of bucketfuls out of the tank to get the smaller numbers? If all large even numbers are possible, then shifting the number line down 26 at a time, any even number at all should be possible. Said differently, imagine the entire number line folded upon itself, forming a loop 26 units long. Any point on the circle corresponds to that number + 26⋅x. Since 26 and 16 share a factor of 2, all the numbers have to be even, but without that factor, 8 and 13, they're coprime, which means you only need to show that 8⋅x modulo 13 gives you every number 0-12. Multiply those by 2 and unroll the number line back out into a line, and you've shown that any even number of liters is possible.
This is where my ability runs out. How to prove that the modulo function acts like a loop, and that two coprime numbers a,b give every number less than b by k⋅a mod b is beyond me, but a good start.
Question provided by Tim Hsu
Like in any other true engineering household, last night my dad referred me to this question, and the two of us spent maybe half an hour trying to find a good solution to it. Realize that he's taking this class as one of the last prereqs for getting into graduate school as a math major, and I just finished multidimensional calculus, so I won't be able to formally prove it to the rigor technically required.
We started shooting at the easiest targets. Every multiple of 16 and 26 are possible. These numbers can be expressed simply as 16⋅x and 26⋅y, with x and y being positive integers. You can also add some of one and some of the other, so really the numbers possible were more along the lines of 16⋅x + 26⋅y ≥ 0. Then considering that bucketfuls can also be removed from the Tank, you end up with 16⋅x + 26⋅y − (16⋅z + 26⋅w) ≥ 0, with z and w also positive integers.
The final solid progress we made was realizing that adding in a bucket, then removing it was pointless, so the formula can be simplified farther to be 16⋅x + 26⋅y ≥ 0, x and y only contrained to be integers. We also ended up making conjectures that we cannot make any odd number of liters in the tank, and my dad theorized that you'll reach some point when every even number is possible, taking the last conjecture into consideration (ie {every even number} ≥ n).
That's all well and good, but we haven't really said anything that can be proven mathematically. It wasn't until I was laying in my bed later that I really broke the question:
If at some point ≥ n all even numbers are possible, what's keeping us from just taking some number of bucketfuls out of the tank to get the smaller numbers? If all large even numbers are possible, then shifting the number line down 26 at a time, any even number at all should be possible. Said differently, imagine the entire number line folded upon itself, forming a loop 26 units long. Any point on the circle corresponds to that number + 26⋅x. Since 26 and 16 share a factor of 2, all the numbers have to be even, but without that factor, 8 and 13, they're coprime, which means you only need to show that 8⋅x modulo 13 gives you every number 0-12. Multiply those by 2 and unroll the number line back out into a line, and you've shown that any even number of liters is possible.
This is where my ability runs out. How to prove that the modulo function acts like a loop, and that two coprime numbers a,b give every number less than b by k⋅a mod b is beyond me, but a good start.
