TNDOT Friday 9: Combinatorics

by

October 4, 2024

12:21 pm

38 Comments on TNDOT Friday 9: Combinatorics

TNDOT

, , ,

We’ll go back to the old days soon enough, but here is something much more recent. The following question is from the first 1945 Pure Mathematics Victorian matric exam. Some details about the exam(s), and a question for readers, are below.

6. The Matriculation Examination comprises 23 subjects, amongst which a candidate may freely choose. In how many ways can he select four of them?

If the time-table for those subjects comprised 11 sessions, at 10 of which 2 subjects were examined and at 1 of which 3 subjects were examined, what would be the probability of a random selection of 4 subjects not clashing with the time-table?

Now, a few notes for the history buffs, and then a question for TNDOT fans. I know close to zero about the matric exams of that (or any) period, but my guess is that students were required to take five subjects, with English compulsory (as was the case for my HSC in the 70s). That is presumably the reason for the emphasis on “four” in the first part of the question.

There were two Pure Mathematics exams in (December) 1945 and presumably students were required to attempt both papers. The first paper consisted of ten questions and the second of nine questions, each paper was three hours and the instructions on the two papers were identical:

All the questions may be answered. But candidates are strongly advised to submit careful answers to about seven or eight questions rather than hurried answers to a larger number. 

The questions and parts of questions marked with an asterisk (*) will carry somewhat greater weight, particularly in the award of Honours.

Mathematical tables and graph paper to be provided.

The question selected above was not an asterisked question.

There was also a third, “Qualifying exam for honour school of mathematics”, also three hours in length.

Finally, a question for TNDOT fans. So far, I’ve just been fishing around, selecting the questions that most interest me, for being mathematically meaty or for indicating familiarty with now semi-forgotten techniques. But these old exams also contain plenty of pedestrian and/or weird and/or dated questions. I’ve also so far ignored “geometry” entirely, since in the early days it appeared to be largely reciting proofs from Euclid. What this means is, even if these TNDOT are indicating something very interesting about (Victorian) senior mathematics from long ago, it is also giving a distorted picture of that past.

So, what should I do? I could post an entire old exam for one TNDOT, or for every TNDOT. (I think the exams are way old enough that VCAA is not likely to worry.) My concern is that if I do so then readers may not properly concentrate upon any of the questions. These questions obviously require thought, and I think it is valuable to be presented with just one or two questions, and you then either work on it or you don’t. There is no temptation to flit between N questions, focussing upon none. Maybe work though exam by exam, with maybe three questions per TNDOT? I’m open to all suggestions.

 

UPDATE (12/10/24)

This solution will follow morgan, who has presented it very nicely. Thanks also to Rob and Rusty Polly.

The first part is easy, simply requiring the computation of \boldsymbol{\binom{23}{4}} (albeit without a calculator):

\color{blue}\boldsymbol{\binom{23}{4}=\dfrac{23\times22\times21\times20}{4\times3\times2\times1}= 23\times11\times7\times5= 161\times5 \times 11 = 805\times11= 8855\,.}

For the second part, we want to count how many ways the four exams can be chosen without conflict. There are 23 slots in which the 4 exams might fall, and we want to count the number of ways the 4 slots can be chosen to all fall in different sessions. We now need to consider two cases.

CASE 1 

Suppose all four exams occur in the two-exam sessions. There are then \boldsymbol{\binom{10}{4}} choices for the four sessions. And, for each session there is a choice of 2 slots. So, the total number of such choices is

\color{blue}\boldsymbol{\binom{10}{4}\times 2^4= \dfrac{10\times9\times8\times7\times 16 }{4\times3\times2\times1}= 10\times 3 \times 7\times 16\,.}

CASE 2 

Suppose one of the exams occurs in the three-exam session. There are then \boldsymbol{\binom{10}{3}} choices for the other three sessions. Accounting as well for the choice of slots within each session, the total number of such choices is

\color{blue}\boldsymbol{\binom{10}{3}\times 3\times 2^3= \dfrac{10\times9\times8\times3\times 8 }{3\times2\times1}= 10\times 3 \times 4\times 3\times8\,.}

Summing, the total number of non-clash choices is

\color{blue}\boldsymbol{\left[\binom{10}{4}\times 2^4\right]+\left[\binom{10}{3}\times 3\times 2^3\right]= 10\times 3 \times 16 \times(7 + 6) = 10\times 3 \times 16 \times13\,.}

Then, for the probability of a non-clash selection, we divide by \boldsymbol{\binom{23}{4}}, giving

\color{blue}\boldsymbol{\dfrac{10\times 3 \times 16 \times13}{23\times11\times7\times5}=\dfrac{2\times 3 \times 16 \times13}{23\times11\times7}=\dfrac{6\times 208}{161\times11}=\dfrac{1248}{1771}}\,.

A final comment. I guess I can understand why people were less interested in this question. Even without considering the required arithmetic, however, I think this question is significantly trickier than such questions set these days. Imagining this question were set on an exam now, what percentage of students might answer correctly? Even with a CAS in hand, I’d suggest the percentage would be very low.

Visited 65 times, 1 visit(s) today

Related Posts

38 Replies to “TNDOT Friday 9: Combinatorics”

  1. Marty – do what interests you. It is your blog.

    But if you want a suggestion for what you *could* do – I’ve noticed a few of these older papers (pre-1945) had quite a bit of polynomial or algebraic division which I think would stump the majority of students nowadays (CAS is only one reason for this, albeit a very big one).

    As an example – there was a question from 1873 posted elsewhere some time ago to divide 8a^3+27b^3+18ab-1 by 2a+3b-1. The implication may have been that the second expression was a factor, but this was not given in the question.

    There also seem to have been quite a few questions on cyclic polynomials in multiple variables. Also interesting when taken as a set, also interesting on their own.

    Option 3 is to take any old paper (say 1900 as a nice round year) and post one question each day.

    Reply

    1. Thanks, RF. Best to not confuse by posting new questions in comments.

      I know there’s plenty of topics/techniques, such as cyclic polynomials, that i’ve touched upon but could do much more extensively. The question is whether people want lucky dip, or systematically going through an exam, or systematically covering a topic/technique, or just don’t care that much which.

      Reply

      1. A couple in sequence on similar topics are always good (thinking back to the trigonometry ones that had similar approaches, but still subtle differences)

        But other than that, I think the discussions are all useful, the questions themselves just need to be nothing like contemporary exam questions if possible.

        Reply

  2. Seems like y11 methods deals with such questions, then students are spared from it in vce exams. Not so in nsw hsc, where , at least extention maths has always a spot for combinatorics (and sequences, series, more limits).
    Once in my teaching i managed to squeeze in selections with repetitions, and for what purpose?
    I assume numerical(and fraction in its simplest form) required?
    Betting on \frac{1248}{1771} for part 2.
    Feels better if problems like this are among 8 to be done.
    Though it is easy to mis- count options…

    Reply

  3. Where do you find these papers? Readers might be interested in exploring them.

    What does TNDOT mean?

    Did the geometry questions involve “reciting proofs from Euclid” or applying results from Euclid?

    Reply

    1. (1) University of Melbourne Library and State Library of Victoria.

      (2) Teaching New Dogs Old Tricks.

      (3) I have read that in the early days, 1860-ish, the intent was to be able to reproduce proofs from some given edition of Euclid, to the word. I have not looked looked closely, but the early 1900s seemed to be to reproduce proofs of theorems from Euclid, although I’m not sure that the “to the word” condition was still being enforced.

      Reply

      1. It was mostly Euclid’s elements Books 1 and 2 (and this seems to be because that is what the Oxford and Cambridge exam papers did). In some of the British exams (available online, just search for Cambridge entrance examination) the paper was actually called Euclid.

        Reply

      2. I don’t teach VCE mathematics, but I suspect that many VCE students could not reproduce proofs of anything these days. Have they ever seen a proof? Could they prove Pythagoras’s theorem?

        When I was at school, text books on Euclidean geometry tended to ask the reader to solve problems that involve applying results from Euclid’s “Elements”. I would say that very few teachers have studied “Elements” past Book 1; indeed, I’d go further and say that many teachers do not know who Euclid was. It is a beautiful work.

        Reply

        1. BTW, once I taught a course out of Maxwell, E. A. (1949). “Geometry for advanced pupils”, OUP. Some of the exercises are questions from examination papers. None of them involve reproducing proofs from Euclid’s “Elements” although some questions ask student to prove propositions.

          Another book that looks interesting is Posamentier, A. S. & Salkind, C. T. (1988). “Challenging problems in geometry”, Dover. And they also have written “Challenging problems in algebra”, Dover.

          Reply

          1. (Sarcasm) But Marty… Specialist now has proof by induction, contradiction etc assessable in exams…

            (Not sarcasm) Australian (excluding NSW and ACT), to be a bit more precise.

            Reply

    2. The State Library of Victoria is the best place. Most of them you just put in an online request and they are delivered to the reading room by 10am the next day. Some of the older ones you need to phone up 2 days in advance as they are in offsite storage.

      Only problem is they are bound in volumes with all the other exams, so you need to flick through all the Latin, British History etc exam papers to find the various Mathematics ones.

      Anything past about 1965 is via the public records office in North Melbourne, but the State Library also has most (but not all) years.

      Reply

  4. This one does not appear to have attracted much interest. It was not clear to me that it was so straight-forward. can anyone confirm that RP is correct and/or wish to suggest a solution?

    Reply

    1. Straightforw answer for part one,
      ^{23} C _{4}
      This evaluates to:
      \frac{23 \cdot 22 \cdot 21 \cdot 20}{1 \cdot 2 \cdot 3 \cdot 4} = 253 \cdot 35 = 8,855

      I think it is worth showing students a shorter way to calculate ^{n} C _{k}.
      C _{0} , C _{1} are obvious,
      C _{2} a must, C _{3} handy,
      C _{k} may be helpful.

      Reply

        1. I often go back to interpretation, ” in how many ways can you choose 1 object from among 10 distinct…”, and it generally fixes the issue

          Reply

    2. It is not that this question is of lower quality than other TNDOT posts (opinion). It is more that such questions still occur at times in VCE/HSC/Whatever papers. I for one am more interested in the types of question that are just not seen any more or require thinking in ways that the VCE curriculum does not encourage (OK, that could be a long list, but I think you get my point).

      Reply

      1. Fair enough. But is this question that obvious to do neatly? I only looked quickly, but it didn’t seem so to me.

        Reply

        1. I didn’t give it too much thought to be honest. Combination of Year 12 students in their final week(s) before exams, other random school crap being dumped on us all and combinatorics is not something that interests me that much.

          Not a bad question, just didn’t spike my interest in the way the algebra/trigonometry ones have.

          Reply

        2. Hi Marty and other commenters. Can someone please confirm the answer to part 2 of the combinatorics question? Thanks

          Reply

          1. Thanks, Rob. I’m waiting for commenters to provide something concrete. I guess RF is sort of correct, that the question is somehow less otherworldy than previous TNDOTs. But I think he is underselling the question somewhat. I’m not sure most SM students would be capable of solving it.

            Reply

                  1. So, winning selection either has (a subject from threesome and 3 from twosome) or (4 subjects from 2some). To account for these, we choose 4 sessions. Latter is easier,
                    ^{10}C _{4 } \cdot 2^{4}
                    , as there are 2 choices in each session.
                    Similarly in former:
                    ^{10} C _{3} \cdot 2^3 \cdot 3

                    Reply

                    1. Sorry, RP, I’m lost. I’m not sure what the “latter” is easier than. Compared to what? Are you commenting on morgan’s solution?

        3. As others have said, the first part is simple

          \binom{23}{4}

          For the second part, the main difficulty is working out how to approach the problem (which I feel is often the case with these types of problems). Once you’ve done that it’s fairly straightforward. In this case, you need to realise that for the second part you need to find out how many ways you can select four subjects with the restriction that you can only choose one subject from each group. To do that, split into to cases:
          Case 1: All subjects from 10 groups of 2: 10 groups, choose 4, 2 ways to choose the subject in each group gives:

          \binom{10}{4}\cdot2^4

          Case 2: One subject from the group of 3, rest from the groups of 2: 3 ways to choose from the group of 3, 10 groups, choose 3, 2 ways for each group gives:

          3\cdot\binom{10}{3}\cdot2^3

          Add them together and divide by the number of ways of selecting subjects with no restriction

          \left(\binom{10}{4}\cdot2^4+3\cdot\binom{10}{3}\cdot2^3\right)/\binom{23}{4}

          Plug that into the calculator and you get

          \frac{1248}{1771}

          Though in 1945 that would’ve required a bit more work. But

          \left(\frac{10!}{4!6!}\cdot2^4+3\cdot\frac{10!}{3!7!}\cdot2^3\right)/\frac{23!}{4!19!}

          simplifies easily enough to

          \frac{13\cdot3\cdot2^5}{23\cdot11\cdot7}=\frac{1248}{1771}

          Alternately you could simply to a probability tree:

          P(\textrm{no clash})=\frac{20}{23}\times\frac{18}{22}\times\frac{16}{21}\times\frac{14}{20}+\cdots

          \frac{20}{23}\times\frac{18}{22}\times\frac{16}{21}\times\frac{3}{20}+\cdots

          \frac{20}{23}\times\frac{18}{22}\times\frac{3}{21}\times\frac{16}{20}+\cdots

          \frac{20}{23}\times\frac{3}{22}\times\frac{18}{21}\times\frac{16}{20}+\cdots

          \frac{3}{23}\times\frac{20}{22}\times\frac{18}{21}\times\frac{16}{20}

          P(\textrm{no clash})=\frac{20\times18\times16}{23\times22\times21\times20}\left(14+3\times4\right)=\frac{26\times20\times18\times16}{23\times22\times21\times20}

          Again, simplifies easily enough.

          Reply

          1. Thanks, morgan. So by a vote of 2 to 1, the answer is 1248/1771.

            I’ll check your working tomorrow, but it was exactly that kind of fiddly division into cases that seemed a little tricky here.

            Reply

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