Gelfand’s Algebra and an Application of the Greedy Algorithm

One of the joys of working with children learning mathematics (that means all of us) is to witness the accidental discoveries that they make. Let me narrate my experience of that in this rather long post.

The only way to learn mathematics is to do it. And doing mathematics is solving problems. In a delightful book that I will come back to at the end of this article, the following problem appears (reproduced here verbatim):

Problem 1. Several digits "8" and some "+" signs are inserted to get 1000. Figure out how it is done. (For example, if we try 88+88+8+8+88, we fail because we get only 280 instead of 1000).

Try to solve it before reading further (I have inserted a space-filling image below 😊). I guarantee, it would be a lot of fun. It will also be fun if you ask it to a ten- or eleven-year old and observe what she does.

Photo by Anna Tarazevich on Pexels.com

Rujuta started to think about how to solve it. “Hmm, let’s see”, she said. After a few minutes (which we both spent patiently, as I was also trying to solve it in my head; this was not a material that I had reviewed before the class).

“Maybe I’d start with the largest number that is all 8’s but which is less than 1000”, she said somewhat speculatively. “That’s interesting, sure”, said I.

“That would be 888, which means I have 1000-888 = (after some time lag) 112 remaining”, she added.

[Here, she actually made a few calculation errors, but don’t get me wrong, she had no conceptual misunderstanding. Sometimes she ends up saying or writing 76 even if she means to say 66, or thinks of 72. Do you know if this is some kind of peculiarity that some people have especially with numbers?]

“Cool, now, we have 112 that we need to get using only 8’s”, was her next thought.

I was just witnessing her “thinking out loud process” and nodding to her efforts.

“That would be one 88 and now we have 12 + 12 = 24”.

“Ah, that is three 8’s”, she said, and then wrote, “888+88+8+8+8 = 1000“. She was giggling all along and as she finally discovered the solution, she was very happy.

Quite frankly, I was stunned. I had made (quietly) the mistake of expecting her not to do it so fast (yet another reason we should get rid of expectations of any kind).

And as I witnessed it happen, I was very happy as well. I said, “Wow! You did it, and in doing so, you accidentally discovered, or perhaps invented a technique called The Greedy Approach of problem-solving. This approach provides elegant solutions to several problems, although, at times, it may lead you astray. For example, how do you know beforehand if you would end up into 24 which is just three 8’s? Of course, you don’t, but you just press on in the hope that it may work in the end.”

She agreed with me. Indeed, the so-called greedy approach is effective is many situations.

Did you solve this problem this way? Perhaps you did. It is also possible that you solved it differently. No despair. All solutions are interesting. The problem itself is perhaps trivial for mathematically advanced students, nonetheless, it is very interesting.

I then proceeded to ask her, “What if the sum were 2000? Would you still use your greedy technique? That is, would you still look for the largest all-8’s number smaller than 2000 (which is still 888) and so on?”

She thought for a few moments and said, “Well, I need 2000. That is 1000+1000. I have already solved the problem for 1000 and I can solve it once more: 888+88+8+8+8 + 888+88+8+8+8. Isn’t it?”

I was pleased to say yes. This was indeed a useful observation. We then went on to think of what will happen were the sum 10000. She tried with 8888 first (she said that that was the largest all-8’s number smaller than 9000), arranged to get the remaining 112 (9000-8888) as 88+8+8+8 and then since she had already solved the problem for the sum = 1000, she reused that part of the solution.

After hearing both these answers I told her a mathematician joke:

A physicist and a mathematician are sitting in a faculty lounge. Suddenly, the coffee machine catches on fire. The physicist grabs a bucket, leaps toward the sink, fills the bucket with water, and puts the fire out. The next day, they are sitting in the same lounge. Again, the coffee machine catches on fire. This time, the mathematician stands up, gets a bucket, and hands the bucket over to the physicist, thus reducing the problem to a previously solved one.

Then I said to her, “That makes you a mathematician.” And she just chuckled.

The problem is taken from a book, Algebra, by two well-known mathematicians, I. M. Gelfand and A. Shen. This is a brilliant book for School Algebra (and beyond). I recommend at least referring to this book when introducing Algebra to middle school students. Here is the mathematician Richard Askey’s review of this book.

We went on to see their solution and here’s its verbatim reproduction:

Solution: Assume that
...8
....
....
...8
____
1000
We do not know how many digits are used in each number. But we do know that each number ends with "8" and that the last digit on the sum is "0". How many numbers do we need to get this zero? If we use only one number, we get 8. If we use two numbers, we get 6 (8+8 = 16), etc. To get zero we need at least five numbers:
....8
....8
....8
....8
....8
_____
1000
After we get this zero, we keep "4" in mind because 8+8+8+8+8=40.
To get the next zero in the "tens place" from this 4 we need to add at least two 8's since 4+8+8=20.
   8
   8
   8
..88
..88
____
1000
We keep "2" in mind and we need only one more "8" to get 10:
   8
   8
   8
  88
 888
____
1000
The problem is solved: 8+8+8+88+888=1000.

It is clear that the authors are subtly trying to introduce Algebra to middle schoolers. I went over this solution with her and she appreciated it, but quite naturally, she liked her own solution more!

I do think that the solution presented in the book has become (perhaps subjectively speaking) a bit more tedious than the greedy approach that Rujuta found. For example, it is not immediately clear if we need to take five 8’s or ten 8’s (or fifteen or twenty 8’s) to yield the zero in the units place of the sum since both satisfy the condition: 8×5=40, 8×10=80. Similarly, with the 4 carries, to get the zero in the “tens place” with two 8’s (as demonstrated above, 4+8+8=20) or with seven 8’s (4+8+8+8+8+8+8+8=60). We will clearly choose 4+8+8 first, but the point is that we need to examine many more cases (it appears to become like searching in a “tree”).

I let Rujuta know that I liked her solution more than the great Gelfand’s solution and she was somewhat flattered. But more importantly, she looked content. She looked happy. I thought she may enjoy such exploration more even though it is expected to be challenging. In the end, maybe, just maybe, the endeavor would turn out to be worthwhile. I had my little experience of what Francis Su calls Mathematics for Human Flourishing.

That, I thought was priceless.

Leave a comment

Design a site like this with WordPress.com
Get started