I wanted to follow up, at last, on this homework problem a friend had.
- Someone Else’s Homework: A Solution introduced the problem and presented my first draft of an answer.
- Someone Else’s Homework: Some More Thoughts presented my revised thoughts. And the proof I’d turn in if I needed to. Or that I’d put on the answer key if I were writing one.
The question: suppose you have a function f. Its domain is the integers Z. Its
rage range is also the integers Z. You know two things about the function. First, for any two integers ‘a’ and ‘b’, you know that f(a + b) equals f(a) + f(b). Second, you know there is some odd number ‘c’ for which f(c) is even. The challenge: prove that f is even for all the integers.
My friend asked, as we were working out the question, “Is this hard?” And I wasn’t sure what to say. I didn’t think it was hard, but I understand why someone would. If you’re used to mathematics problems like showing that all the roots of this polynomial are positive, then this stuff about f being even is weird. It’s a different way of thinking about problems. I’ve got experience in that thinking that my friend hasn’t.
All right, but then, what thinking? What did I see that my friend didn’t? And I’m not sure I can answer that perfectly. Part of gaining mastery of a subject is pattern recognition. Spotting how some things fit a form, while other stuff doesn’t, and some other bits yet are irrelevant. But also part of gaining that mastery is that it becomes hard to notice that’s what you’re doing.
But I can try to look with fresh eyes. There is a custom in writing this sort of problem, and that drove much of my thinking. The custom is that a mathematics problem, at this level, works by the rules of a Minute Mystery Puzzle. You are given in the setup everything that you need to solve the problem, yes. But you’re also not given stuff that you don’t need. If the detective mentions to the butler how dreary the rain is on arriving, you’re getting the tip to suspect the houseguest whose umbrella is unaccounted for.
(This format is almost unavoidable for teaching mathematics. At least it seems unavoidable given the number of problems that don’t avoid it. This can be treacherous. One of the hardest parts in stepping out to research on one’s own is that there’s nobody to tell you what the essential pieces are. Telling apart the necessary, the convenient, and the irrelevant requires expertise and I’m not sure that I know how to teach it.)
The first unaccounted-for umbrella in this problem is the function’s domain and range. They’re integers. Why wouldn’t the range, particularly, be all the real numbers? What things are true about the integers that aren’t true about the real numbers? There’s a bunch of things. The highest-level things are rooted in topology. There’s gaps between one integer and its nearest neighbor. Oh, and an integer has a nearest neighbor. A real number doesn’t. That matters for approximations and for sequences and series. Not likely to matter here. Look to more basic, obvious stuff: there’s even and odd numbers. And the problem talks about knowing something for an odd number in the domain. This is a signal to look at odds and evens for the answer.
The second unaccounted-for umbrella is the most specific thing we learn about the function. There is some odd number ‘c’, and the function matches that integer ‘c’ in the domain to some even number f(c) in the range. This makes me think: what do I know about ‘c’? Most basic thing about any odd number is it’s some even number plus one. And that made me think: can I conclude anything about f(1)? Can I conclude anything about f at the sum of two numbers?
Third unaccounted-for umbrella. The less-specific thing we learn about the function. That is that for any integers ‘a’ and ‘b’, f(a + b) is f(a) + f(b). So see how this interacts with the second umbrella. f(c) is f(some-even-number) + f(1). Do I know anything about f(some-even-number)?
Sure. If I know anything about even numbers, it’s that any even number equals two times some integer. Let me call that some-integer ‘k’. Since some-even-number equals 2*k, then, f(some-even-number) is f(2*k), which is f(k + k). And by the third umbrella, that’s f(k) + f(k). By the first umbrella, f(k) has to be an integer. So f(k) + f(k) has to be even.
So, f(c) is an even number. And it has to equal f(2*k) + f(1). f(2*k) is even; so, f(1) has to be even. These are the things that leapt out to me about the problem. This is why the problem looked, to me, easy.
Because I knew that f(1) was even, I knew that f(1 + 1), or f(2), was even. And so would be f(2 + 1), that is, f(3). And so on, for at least all the positive integers.
Now, after that, in my first version of this proof, I got hung up on what seems like a very fussy technical point. And that was, what about f(0)? What about the negative integers? f(0) is easy enough to show. It follows from one of those tricks mathematics majors are told about early. Somewhere in grad school they start to believe it. And that is: adding zero doesn’t change a number’s value, but it can give you a more useful way to express that number. Here’s how adding zero helps: we know c = c + 0. So f(c) = f(c) + f(0) and whether f(c) is even or odd, f(0) has to be even. Evens and odds don’t work any other way.
After that my proof got hung up on what may seem like a pretty fussy technical point. That amounted to whether f(-1) was even or odd. I discussed this with a couple people who could not see what my issue with this was. I admit I wasn’t sure myself. I think I’ve narrowed it down to this: my questioning whether it’s known that the number “negative one” is the same thing as what we get from the operation “zero minus one”. I mean, in general, this isn’t much questioned. Not for the last couple centuries.
You might be having trouble even figuring out why I might worry there could be a difference. In “0 – 1” the – sign there is a binary operation, meaning, “subtract the number on the right from the number on the left”. In “-1” the – sign there is a unary operation, meaning, “take the additive inverse of the number on the right”. These are two different – signs that look alike. One of them interacts with two numbers. One of them interacts with a single number. How can they mean the same thing?
With some ordinary assumptions about what we mean by “addition” and “subtraction” and “equals” and “zero” and “numbers” and stuff, the difference doesn’t matter much. We can swap between “-1” and “0 – 1” effortlessly. If we couldn’t, we probably wouldn’t use the same symbol for the two ideas. But in the context of this particular question, could we count on that?
My friend wasn’t confident in understanding what the heck I was getting on about. Fair enough. But some part of me felt like that needed to be shown. If it hadn’t been recently shown, or used, in class, then it had to go into this proof. And that’s why I went, in the first essay, into the bit about additive inverses.
This was me over-thinking the problem. I got to looking at umbrellas that likely were accounted for.
My second proof, the one thought up in the shower, uses the same unaccounted-for umbrellas. In the first proof, the second unaccounted-for umbrella seemed particularly important. Knowing that f(c) was odd, what else could I learn? In the second proof, it’s the third unaccounted-for umbrella that seemed key. Knowing that f(a + b) is f(a) + f(b), what could I learn? That right away tells me that for any even number ‘d’, f(d) must be even.
Call this the fourth unaccounted-for umbrella. Every integer is either even or odd. So right away I could prove this for what I really want to say is half of the integers. Don’t call it that. There’s not a coherent way to say the even integers are any fraction of all the integers. There’s exactly as many even integers as there are integers. But you know what I mean. (What I mean is, in any finite interval of consecutive integers, half are going to be even. Well, there’ll be at most two more odd integers than there are even integers. That’ll be close enough to half if the interval is long enough. And if we pretend we can make bigger and bigger intervals until all the integers are covered … yeah. Don’t poke at that and do not use it at your thesis defense because it doesn’t work. That’s what it feels like ought to work.)
But that I could cover the even integers in the domain with one quick sentence was a hint. The hint was, look for some thing similar that would cover the odd integers in the domain. And hey, that second unaccounted-for umbrella said something about one odd integer in the domain. Add to that one of those boring little things that a mathematician knows about odd numbers: the difference between any two odd numbers is an even number. ‘c’ is an odd number. So any odd number in the domain, let’s call it ‘d’, is equal to ‘c’ plus some even number. And f(some-even-number) has to be even and there we go.
So all this is what I see when I look at the question. And why I see those things, and why I say this is not a hard problem. It’s all in spotting these umbrellas.