Witch 94: What Are the Odds?

This is the second of our three WitCHes on VCAA’s Specialist Mathematics Exam 1 Sample Questions. It may not be quite bad enough for a WitCH, but it’s very not good. Our main reason for posting it is because we believe there is more in the question than might meet a teacher’s eye. As with our previous WitCH, this question is on a new topic, and some visible discussion seems worthwhile.

UPDATE (14/02/23)

No one ever pays attention to the titles. Anyway, on to the question, which is a disaster (and is worded horribly).

As many commenters have noted, below and here, there is absolutely no point in a proof by contradiction, since the question can easily and naturally be proved directly. Plus, the proof by contradiction highlights an issue, which VCAA ignores but which is worth at least some consideration, and which highlights a(nother) major VCAA failing.

First the direct proof, and for this let’s make clear our definitions: an integer n is even if we can write n = 2k for another integer k; and, n is odd if we can write n = 2k + 1 for an integer k. This stuff may seem “well, duh”, but, as we will discuss below, it is not.

Now, for the direct proof, we are assuming n is odd, which means we can write n = 2k + 1. So,

n3 + 1 = (2k + 1)3 + 1 = 8k3 + 12k2 + 6k + 1 + 1 = 2(a bunch of integer stuff).

Done.

What about a proof by contradiction? Well, that requires assuming there is an odd integer n for which the conclusion “n3 + 1 is even” is false, which would mean n3 + 1 is odd. Is that possible? Well, remembering that n is odd, we can write n = 2k + 1. Then, calculating exactly as we did in the direct proof, we find that n3 + 1 = 2(integer stuff), which is therefore even. But we assumed n3 + 1 was odd, and so we have a contradiction. Done.

There are two points to make about this proof by contradiction. The obvious point is that there is no point. The fundamental content of the proof is identical to that of the direct proof. The contradiction proof simply cloaks the direct proof in a layer of gratuitous and confusing logic. (Incredibly, the webinar makes the contradiction proof even worse.)

The second point to make is that the contradiction proof above is fallacious. Remember that “well, duh” stuff above?

In the proof by contradiction, we assumed the conclusion “n3 + 1 is even” is false. But the negation of that statement is “n3 + 1 is not even“. Now, does an integer being “not even” imply that it is odd? Yes, but it takes a proof.

What is missing from the proof by contradiction above is a proof of, or at least a clear statement that, every integer is either even or odd. This can done easily, and nicely, by induction.

Should students simply be able to assume that “not even” means odd? How would they know? Should they then then also be able to assume ODD x ODD = ODD? If so, there is an even simpler direct proof of the n3 + 1 thing.

When setting out proof as a topic, it is a fundamental responsibility to clearly lay out the ground rules. VCAA has, instead, provided a swamp.

43 Replies to “Witch 94: What Are the Odds?”

  1. Thanks for making a WiTCH out of this Marty – I have two specific gripes about the question, but I do not pretend to fully understand the deeper issues that may be at play.

    1. Minor gripe. Why would anyone prove this by contradiction? A direct proof is simple, easily understood and sufficient. Failing that, proof by induction would be a suitable choice. Contradiction though…

    2. Major gripe. Proof by contradiction in this question has too many potential stumbling blocks. Suppose a student assumes that n is even to begin with. Then what do they prove? That n^{3}+1 is odd? What does that achieve? If we assume that n is odd and assume that it is possible for n^{3}+1 to also be odd – that is just the direct proof. No contradiction required.

    If the question simply asked “prove X” then it would be fine.

      1. I’m not clear on exactly what to assume in order to prove a contradiction.

        If you assume too many things are false, you may end up with a proof by contrapositive which is not the same as a contradiction.

          1. Contrapositive: to prove A implies B, prove the contrapositive not B implies not A.

            Example, to prove x^{2} is even implies x is even, prove that x is not even implies x^{2} is not even.

            No contradiction involved.

            Using logic language (and I’m VERY rusty on this…)…

            proof by contradiction involves proving that (Not(Not(P)) implies P.

              1. That is the central point of my second gripe.

                To prove statement P by contradiction, we have to assume Not P.

                In this case, I’m not exactly clear on what Not P is. Mostly because the statement we are trying to prove is an implication.

                For example, do we assume that when n is even then n^{3}+1 is odd and show this leads to a contradiction, or do we assume that when n is odd then n^{3}+1 is odd? It all just seems a bit pointless an approach.

                1. You didn’t answer my question. You gave an example statement and you outlined, correctly, how to prove the statement by instead proving the contrapositive. Can you also prove that statement by contradiction? If so, what would be the structure of the proof?

                  1. I’m not entirely sure. It would be either:

                    Assume it is possible for n to be odd and n^{3}+1 to also be odd.

                    Or:

                    Assume it is possible for n to be even and n^{3} to also be even.

                    In the first case, if n leaves a remainder of 1 when divided by 2, then n^{3}+1 will not, hence contradicting(?) the assumption that n^{3}+1 is odd.

                    In the second case, if n leaves no remainder when divided by 2 then n^{3}+1 will leave a remainder of 1 when divided by 2. Also a contradiction (maybe?)

                2. Just to be clear, let’s stick to your statement:

                  If x2 is even then x is even.

                  I want you to give the structure of a proof by contradiction for this statement. If you’re not sure, I’d suggest you still give it a go. If you really don’t want to give it a go, that’s fine: I’ll do it.

                  But let’s sort out the basic ideas of how these proofs work, and with respect to your example, before discussing the VCAA question.

                3. “Implication” is a boolean operator (there’s a slight nuance in particular scenarios but in most of mathematics it is one) defined as such:

                  (P implies Q) is false when Q is false and P is true, and true for all other values of P and Q.

                  not(P implies Q) is defined as you’d hence expect.

                  Note that not(P implies Q) is equivalent to (not(Q) AND P).

                  See: https://en.wikipedia.org/wiki/Material_conditional for more context.

  2. Are the terms “odd” and “even” precisely defined by VCAA, and does the new logic area of study actually introduce enough logic to be able to properly answer this question? Have they introduced logical quantifiers to the course?

  3. I suppose they want:

    Assume the negation: that there exists some odd n such that n^3+1 is odd.
    Let n=2k+1, for integer k
    Then n^3+1 = 8k^3 +12k^2 + 6k + 2 = 2(4k^3 +6k^2 + 3k +1)
    Thus, n^3+1 is even. This contradicts our assumption that n^3+1 is odd. Therefore, n^3+1 is even.

    Quite Effing Disastrous.

      1. Ok I looked at their proof… they said the negation is that ‘if n is odd, then n^3 +1 is odd’. (Well, no they didn’t, since they said that proof by contradiction involves assuming the ‘opposite’, and didn’t specify ‘negation’). And look, I haven’t studied logic before (unless you count in Specialist 1+2) but that’s wrong, surely. And then they did exactly what I did but with some LHS/RHS formality that clouded the fact that it was essentially a direct proof… am I missing something? What do you think they’re looking for?

        1. Jesus H. Christ. I forgot how bad the webinar discussion was. Yes, you did what they want.

          The question is bad to begin with, and the webinar, together with Anonymous’s queries, makes it a debacle. Others can give it a go. I’ll get back to it in the next day or so, when I have time to untangle it.

          1. I think you were right the first time, it need not be that bad. Given what they want you to show, say n^3+1 is odd. Then n^3 is even. But odd^3 is odd, so that’s your contradiction.

            The question itself is still very stupid of course.

            1. Yes, that’d be neater. Still kind of contains the direct proof though (‘odd^3+1 = odd+1 = even’, which surely is the most natural way to look at that question). But VCAA would never let students assume things like odd x odd = even; I don’t know that they’d even accept odd+1=even. I was taught that you always have to expand ‘even’ to 2k and ‘odd’ to 2k+1 then do algebra for these kinds of proofs.

              And I’m glad there’s some attention on just how stupid these proof questions are. I remember being excited for proof by contradiction in year 11 and being dismayed when it was all like this…

            2. Of course the proof, even by contradiction, need not be that bad. But:

              (a) You need to consider the madness of VCAA’s proof. This is what aps was trying to reproduce and understand.

              (b) There is a deeper issue, alluded to by Anonymous.

  4. Thanks to everyone who has commented so far. I’ll look to update this and the other SM WitCHes soon (maybe “soon”).

    First, just to tease out another aspect, I have a question: What is an odd number?

    (Note the title to this WitCH …)

    1. OK – I’ll stick my neck out…

      I would say an odd number is a positive integer which leaves a remainder of 1 when divided by 2.

      Hence, a number of the form 2k+1 where k is a non-negative integer.

        1. Hmmm… the VCE glossary page seems to have moved. Do we assume that the 7 to 10 document applies to VCE?

          Or, do you have a link to the new location?

          1. Was there a VCE glossary? I mean the K-10 glossary, although it would also be interesting to see what the textbooks say (if anything).

    2. OK, let’s try to keep this moving.

      The glossaries (VCAA and ACARA (Word, idiots)) define “odd” to be “not even”.

      The Specialist textbooks (Cambridge, Jacaranda and Nelson) define/take “odd” to be of the form 2k + 1, with k an integer.

      Is this a problem?

      Is it a problem for VCAA’s proof by contradiction problem above, as proved in their webinar?

      (Yes, the main problem is that the proof is ridiculous. But try to focus.)

      1. There are plenty of numbers that are “not even” which are also not “odd”.

        Hence, Yes, defining “odd” as “not even” is a problem.

        But I suspect there are other issues at play here.

      2. OK, let’s try this. Let’s accept that an odd number is an integer of the form 2k + 1 (k an integer). That’ll be our definition, consistent with all the VCE texts.

        We’re trying to prove the sample exercise above by contradiction. So \boldsymbol{n} is odd and we assume (in order to arrive at a contradiction) that “\boldsymbol{n^3+1} is even” is false. That is the assumption we will contradict is

        *) \boldsymbol{n^3+1} is not even.

        Now what? We’re assuming this number is not even. Do we then know this number is odd? Why?

        1. Directly applying the division theorem proves that an integer being odd is equivalent to it not being even. Alternatively it probably wouldn’t be too hard (not necessarily for the average specialist maths student) to prove that fact using induction or some other method.

          1. Yes, exactly. Except:

            (a) The need to prove (or assume) anything hasn’t crossed anyone’s mind, including at VCAA;

            (b) the division theorem is not a given, it’s a theorem.

            1. One would hope that VCAA would provide a list of theorems or facts that can be assumed, though that seems unlikely.

              VCAA has half-assed pretty much all the mathematics in VCE, which has created lots of problems, but it still has been okay for students and teachers who don’t care about mathematics in any way outside of getting good results in VCE.

              However, now, they’re introducing logic and proof, and they’re half-assing it again. The problem is that logic and proof can’t be half-assed without the entire “area of study” becoming meaningless.

              I predict the following: the exam questions related to logic will follow some “formula”, with almost all questions falling into a set number of archetypes. Students will just memorize the “formula” for a proof for each archetype (which may or may not be correct, what matters most to students and teachers is whether it will get them full marks in the exam), without actually understanding what they are writing. I think a lot of people already do that for a lot of the MCQ in exam 2.

    1. Mine was too flippant a reply. The chess gambit is a great analogy, and most (pure) mathematicians would appreciate proofs by contradiction in the same manner. Nonetheless, I think you might be misrepresenting Hardy.

      The point of using a proof by contradiction is because it is natural, or effectively essential, to do so. I don’t know of mathematicians who employ such proofs simply because they like that style of proof. There might be some of that going on, and in particular from Hardy, but it hasn’t been my experience. In brief: if you can compute then you compute.

  5. Marty,

    Agreed as i said,” Here though it is unnecessarily complicated…” (to use proof by contradiction).

    Nevertheless, I am a big fan of G H Hardy and have an inherited a first edition copy of his “A Mathematician’s Apology (1940)” mentioned in the link above.

    A fine read IMO for most aspiring students in prime number theory, combinatorics, and history of mathematics.

    In the book he mentions “reductio ad absurdum” to be one of a mathematician’s finest weapons

    A great pure mathematician and collaborator with Littlewood and Ramanujan as well as a colleague of Bertram Russell

    Steve R

Leave a Reply

Your email address will not be published. Required fields are marked *

The maximum upload file size: 128 MB. You can upload: image, audio, video, document, spreadsheet, interactive, text, archive, code, other. Links to YouTube, Facebook, Twitter and other services inserted in the comment text will be automatically embedded. Drop file here