A very puzzling proof

I have an abiding (if amateur) interest in mathematics, one reason being that (in all modesty) I am good at it.

While my interest a decade back was in problem-solving, I find I am unable to concentrate hard enough to dispatch the problems that would have hardly teased me back then. It’s a worrying trend, and one reason why I want to do the Ironmind.

But I digress. My interest now is primarily in what I would call the ‘philosophy of mathematics’ and this post is about a very interesting proof to an interesting theorem. I first encountered this theorem in high school mathematics, so it’s hardly the dizzying heights of mathematics.

The problem is simple enough to state: Prove that the product of ‘r’ consecutive numbers is divisible by r! (r factorial).

For example, if we pick 5 numbers 83, 84, 85, 86 and 87, we need to prove that their product (83x84x85x86x87) is divisible by 5! (1x2x3x4x5).

The textbook proof to this theorem is using a double-barreled induction, once over the starting number in the sequence and once over the number of numbers in the sequence. It’s a bit tedious, but otherwise not particularly difficult.

I only state this because I want to communicate that yes, this theorem is correct, that it can be proved without any controversy.

Now onto the controversial part.

When I was in class 12, my mathematics teacher gave us a very cute proof of this theorem.

He said, consider the value:

If we can prove that this is an integer, it means the numerator is divisible by the denominator.

Now for a moment, let’s consider a different problem. Say we have 87 people in a room, and we need to pick 5 of them for a lunch treat. How many ways do we have to do this?

We can pick the first person in 87 ways, the second in 86, the third in 85, the fourth in 84 and the fifth in 83 ways. But if we do that, we’ll have repetitions because the order in which we pick people is not important. How many repetitions will we have? This is the number of ways in which we can arrange 5 people, which is 5 times 4 times 3 times 2 times 1.

So the effective number, which is known in high-school mathematics as 87 C 5, or in notation form,

It’s the same number!

And because it represents the number of ways in which we do something, it has to be an integer. You can’t have 8 and a half ways of choosing people, right?

So it’s a neat little proof.

For a very long time since I heard this proof, there was something gnawing at the back of my head about it. I felt there was something a bit spooky about this proof, but I couldn’t put my finger on it.

And then I realized something weird.

This is a different proof because it is an experimental proof of a theorem.

Can you believe that? An experimental proof of a mathematical theorem.

The proof doesn’t base itself on the underlying axioms of mathematics.

It bases itself on the underlying realities of our universe.

The final statement in the proof – the climax – is not that this theorem is the last link in a chain of deductions reasoned from a set of axioms using a set of logical steps.

The climax in the proof is: this number represents a countable quantity in the real world, so it must be a countable number.

Which is very, very weird.

What do you think?

Advertisements

11 thoughts on “A very puzzling proof

  1. Last year while camping, I picked up a whole lot of small stones and was trying to arrange them into patterns. The goal was to see if there was a ‘physical’ way to find if the number of stones I had was prime, without knowing exactly how many there were.
    When I read this post, thats what came back to me- whether similar to this concept of ‘knowing’ that the number of ways to pick 87 students is an integer, one could know if a set of objects constituted a prime number without knowing how many there were……

    1. Interesting – though I don’t know if is appropriate to call it a proof we should recognize and appreciate it for what it is – a fine example of lateral thinking which is extremely hard to fine in the classroom

  2. Good one! It feels like there is a “leap of faith” kind of reasoning in your teacher’s “proof”. It is not a proof- it’s an appeal to intuition and that can sometimes be dangerous. He states the question as “How many…” and the answer is in the question itself since the connotation is that the answer is countable! This is something only humans can understand, without proof, because of the learned association of meaning to words and phrases in natural language. There is no way I can make a computer understand this line of reasoning, unless the computer can speak English (or Tamil or …) like a normal man, for example. However, being a normal man, I do think these kinds of “experimental” setups are awesome.

    1. I’ve seen this kind of proof in other situations before. The most common is proof of consistency; to prove that a set of axioms is consistent. That is, to prove that they will not result in being able to derive both a statement and its negation. A good way of doing that is to find a ‘physical model’ of the axioms, for example a geometric structure, and ‘conclude’ that since the axioms represent something in the physical world, and the physical world is presumably consistent, so are the axioms.

      I’ll elaborate in a later blog post, but if you’re in a hurry, check out Newman and Nagel’s lovely little book (which is readable even at a high school level), “Godel’s Proof”.

      1. Yeah, agreed. I have seen this as well. But such reasoning cannot be part of a formal system like mathematics. Haven’t read Nagel’s work, but I vaguely recall Hofstatder explaining in GEB such a fallacy using physical representations of points and lines. But in a different “world” , one can derive essentially the same or widely different results using different definitions of basic axioms such as lines and points. Or something to that effect. I do agree that humans have an innate sense of truth based on observations in the physical world which need not be axiomatic. So your example is quite appealing.

  3. Technically speaking, your math teacher’s discussion was not a proof of the theorem you stated at the start of your post. Your teacher creatively demonstrated that the theorem is valid when r = 87, but to prove the theorem he would have needed to demonstrate that the same reasoning and logic would hold regardless of the number of people in the room.

    That said, there is no controversy whatsoever in the methods your teacher used – and it was most definitely based in the axioms of mathematics.

    Thinking of non-negative integers as people is completely valid and mathematically sound. It’s just a substitution; no different than using X or Y. The rules for counting people are exactly the same as for counting non-negative integers.

    Suppose you wanted to prove that for any non-negative integers X and Y, X + Y will always be another non-negative integer greater than X or Y.
    Proof by thinking of non-negative integers as people:

    Suppose a group of people walk into an empty room. A few minutes later, a different group of people walks into the same room. There is now a new group of people in the room which is larger than either of the two initial groups.

    There is nothing wrong with thinking this way as long as you are extremely careful to make sure your substitution is valid – note how I specifically mentioned non-negative integers to avoid the contradiction of ‘negative people’.

    1. Matt, thank you for the x+y example which is, in my opinion, a much simpler and better demonstration of an experimental proof.

      When I said “experimental proof” in my post, I meant that in a specific way. When we do a physics experiment to prove a certain principle – for example, to verify the time period of a pendulum – we do it in a specific time and place, and we assume that the results will be the same whenever and wherever we do it. We take it on faith that physics ‘works that way’ – if it didn’t, we could never have general laws.

      In the case of this proof, we seem to be making a similar assumption with mathematics; though natural numbers can be interpreted in many different ways, we are able to generalize results from one interpretation. One way to interpret natural numbers is as ‘countable quantities’, i.e. quantities that have a one-to-one mapping with any collection that can be counted. Therefore, if we can establish properties of countable objects (for example the fact that adding people to a room cannot decrease the number of people there), we can work backwards to find out the corresponding mathematical properties of natural numbers.

      The question is, how strong (or tenuous) is the link between natural numbers and countable objects? Your comment seems to imply that your point of view is, the link is absolute, and the two are exactly – mathematically, logically – the same.

      I think that’s a good point of view to have. Certainly, if we accept that point of view, the proof becomes less controversial.

      However, I would be wary about taking one interpretation of a mathematical entity and assuming that theorems about the interpretation are also valid theorems about the mathematical entity. I’ll post about this in a geometric context in a few days, which will hopefully give some more clarity about my own position on this.

      1. You are entering the world where the lines between mathematics, physics, perception and reality all fade and lose their distinction.

        The fact is that mathematics has nothing to do with numbers, and one-to-one mappings simply don’t exist without ignoring some property of what you are measuring. The term “natural numbers” is one of the most misleading things we can say. There is nothing natural about them – nothing in nature is actually discrete or countable.

        To count anything and then use arithmetic to manipulate and describe those objects implies that the objects are completely indistinguishable, and that is the huge flaw. And furthermore, every number we use is always in some way an approximation, which further messes everything up.

        My little proof may have demonstrated a rule about non-negative integers, but it says nothing about people – and numbers have no meaning unless they are attached to something. What does it mean to say that 5 people is more than 4 people? How do you quantify a person?

        Ok, I probably could have been more articulate but this is a topic worthy of far more discussion than a blog comment and I need to pull myself from the computer. I will keep an eye out for follow ups and look forward to continuing the discussion.

  4. In mathematics, one would call it a proof by construction. Essentially, if we prove nCr is an integer, the result is immediate. To show that nCr is an integer, we can use an argument by construction (by showing that it’s the number of ways of choosing r items out of n items).

    1. Then, it boils down to the following question: “Does making the assumption that number of ways of choosing is an integer violate mathematical laws?”

    2. But proofs by construction are notoriously unreliable. I’m sure you must have come across the ‘proof’ that all triangles are isosceles using a false construction. This one falls somewhere closer to truth but the proof is just as suspect.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s