Running on Math
My last post was titled Running without Numbers. This time interestingly math was a central feature of my run.
I was out for a run with a friend the other day and he shared a math problem with me. This is yet another confirmation that my life is moving in a positive direction, when two things of my loves become intertwined. The really great part of this story is how much the problem got me thinking. I hope you find some fun in it as well.
Here is how my friend explained it. You have a 40g mass that you can divide into pieces. How can you minimally divide it to be able to mass all the integer values from 1g to 40g on a balance?
Somehow, I knew immediately that this was going to be a fun exploration. I talked out some of my thinking with him and then got stuck. I realized that to mass the 1g amount you would either need to have one of the pieces be 1g or have two pieces that have a 1g difference in mass.
The problem was there were too many possibilities to consider in my head. This is the point in the problem where I like to write, draw and code my thinking. But I was still moving quickly down a rocky path.
Given the constraints I decided to explore the idea of beginning with a 1g cut as that seemed simpler. To be honest it might have also been that my friend encouraged this line of thinking as well in the way a good teacher gives you some scaffolding in the learning process.
Suppose we first cut a 1g piece from the block. To measure 1g is pretty straight forward. It is important to note that the measuring device being employed is a pan balance. So in this case the 1g piece would go on one side and you know you have a 1g object if the the pans are in balance.
At this point I could also measure 39g since that is the mass of the remaining piece of the block. Similarly it is trivial to measure 40g by using both pieces on the same side. With this limited start, I thought about what cut would allow me to achieve 2g. Of course cutting 2g would work. But you could also cut a 3g piece to accomplish this.
Let me explain. If you put the 1g piece on one side of the balance and the 3g piece on the other side, then you can measure a 2g object by placing it alongside the 1g piece.. That means we pick up 3g and 4g as well using the second piece and both cuts together respectively.
Similar to the previous thinking I can also achieve everything up to 4g below the total mass of 40g by placing pieces strategically opposite the remaining 36g piece. So now I have 1,2,3,4,36,37,38,39,40.
To check my thinking I reasoned that cutting a 4g piece for the second cut would not allow the measurement of 2g because there is no way to place 1g and 4g on the balance that would mass this amount.
Next I started thinking about the 3rd cut. To come up with a strategy I tried to generalize the process into an algorithm. This is one of the advantages of computer. I did not use a computer in this case, but the thinking that I did was similar to the thinking I would do to write a program. This is one of the reasons that I get excited about computers as thinking tools.
Here is a way you could think about what I had done to make the second cut. I had taken the total mass of the pieces up to that point which was only 1g. I then doubled that number and added one. That landed me on the choice of 3g.
But you might ask why double and add one? I would offer, that is the largest cut you can make and still get to all the intermediate integers. Let’s keep exploring and see if that makes sense.
So I applied this strategy for the third cut. Doubling four and then adding one. That brings me to 9g. Okay with 9g I can get the 1,2,3,4 from before, but now I can also take those 4g and subtract from 9 by placing them on the opposite side of the balance to mass 5g and using the same combination strategy as before I can get 6,7,8. Additionally, I can also add the 4 grams to the 9g on the same side of the balance. So all the integers from 1 to 13 are possible.
Now the remaining piece is 27g. That actually allows me to get all the other masses 1–40 by subtracting 13 from 27 and adding 13 to 27. But here is the interesting part. If you take the total mass at this point which is 13g, double it and add one you get to 27g that way. So the choice of a 40g block was quite intentional.
Another interesting noticing is that all the piece sizes that I have taken are powers of three: 3⁰, 3¹, 3², 3³. I told my friend that I thought I could now solve this problem for any block of size N.
He seemed skeptical.
Here is my rationale: Start cutting off powers of 3 until you run out of block to cut. The next power of 3 is 81. So with the first 4 pieces you can mass everything from 1–40.
Now with the 81g block you can put those 4 opposite it and get 41g. With similar manipulation you can achieve all the masses from 42g up to 81g. And then continue beyond that all the way up to 81g+40g which is 121g. The next power of 3 is 243 which also follows the rule of doubling the total mass and adding one.
As I ran down the trail all of these ideas were coming together and it felt magical. I was excited that this problem had turned into a wonderful new way of thinking about integers.
I thought about writing down a proof that this strategy could generate all natural numbers on a pan balance. I thought about fact that powers of 3 are equal to one more than the sum of the previous powers doubled. There is probably an interesting conjecture to make about that.
My friend did not seem fully convinced that my answer was full proof. Granted it is hard to fully explicate an idea while running.
He said that he wanted to check if my idea worked using a computer program.
I was confused.
How can we use a computer program to check all the integers to infinity. I started thinking more about mathematical proofs. I am not an expert in mathematics, but I know that the process of proofs in mathematics is quite rigorous and if done well this argument can be made with a good deal of certainty.
So part of the problem is that I lacked the oral skills to make my case. But it is also true that to understand such a proof requires quite a bit of knowledge.
How do we ultimately know that all these mathematical ideas are true if we don’t have sufficient understanding of the proof itself. I guess we have faith in the mathematicians. But it feels like there is a gap somewhere in there.
The one thing I felt quite sure about is that all of these ideas are exciting and engaging. So I did not mind spending more time thinking about them.
When I got home I pondered whether I could start cutting the block with pieces bigger than 1g. I wondered if a computer program could help me think about this more.
So I started with a 10g block and considered all the ways it can be cut. I could have done it on paper, but instead I wrote a little Python program to generate all the possible piece sizes.
n=10
for i in range(1,n):
for j in range(i,n):
k = n-i-j
if k>=j:
print(i,j,k);Here are the piece sizes: 1 1 8; 1 2 7; 1 3 6; 1 4 5; 2 2 6; 2 3 5; 2 4 4; 3 3 4
Then I started thinking about how I might figure out what masses could be balanced with these pieces.
I realized it would take a bit more thinking to come up with this next algorithm, because the piece values can be subtracted or added when measuring a mass on the balance. But as I was looking at the numbers I came to a realization.
The 2g piece can’t be the smallest piece.
Take the example of 10g. If your smallest block is 2g then how would you mass 9g. It is impossible. You need the 1g piece to make 9g.
As I started thinking about it I realized that you need to build up the sequence in precisely the way that I did. Now that does not mean there is only one solution to the 10g block.
As I played with the numbers I realized that both 1,3,6 and 1,2,7 would work. But those are the only two combinations that solve the puzzle. All the others produce holes in the sequence that can’t be filled.
So in the end the approach that I had taken out on the trail was a pretty good one. I can cut any integer gram value block of mass N into the minimal number of pieces to find the mass of all the integer gram values from 1 to N.
