Problem Set 5.1: Combinatorics

Problem Set 5.1: Combinatorics

Question 1

Question 2

Question 3

Question 4

Question 5

Question 1: AMC10 2000 Problem 13

This one is easy – just try it… but can you explain why your answer must be correct?

Question 2: AMC10B 2012 Problem 24

(a)Orient yourself with the problem; draw out a table with one possible solution. Draw another if it helps.

(b)Suppose A&B like song 1, A&J song 2 and B&J song 3 – meeting the ‘pairs’ criterion. What are the possibilities for song 4?

(c)Let’s consider these possibilities for the 4thsong. There are two cases: either a pair of girls likes it, or fewer girls like it. If a pair of girls likes the 4th song, how many ways can we now rearrange which pair of girls likes which song? [Be careful, it’s not just 4!]

(d)Do the same for the second case, in which the 4th song is liked by fewer than 2 girls (so that each song is liked by a different set of girls). How can you rearrange these possibilities?

Question 3: AMC10A 2013 Problem 25

(a)Consider drawing and counting the diagonals of polygons with fewer sides, starting with square, then pentagon, ... do you recognize the numbers?

(b)Obviously each intersection is the result of two lines crossing – how many vertices are ‘involved’ in each intersection?

(c)Still keep thinking of each intersection as choosing n vertices from the polygon - how can you use this idea to calculate the number of intersections?

EXTENSION: Work out the number of intersections, regions and lines in these images – can you find a connection?

Question 4: AMC10B 2014 Problem 24

(a)Let’s solve an easier problem – can you solve the same problem for arrangements of numbers 1 to 4 with sums 1 to 10? Does this tell you anything about the nature of the problem or not?

(b)Now let’s just draw a random arrangement of numbers 1 to 5 – is it true for this arrangement that you can find subsets of adjacent numbers that make all the sums from 1 to 15?

(c)Which sums do you not have to check you can make (because you always can)?

(d)Using the idea of symmetry, you can reduce your check even further – for example, what is checking for a sum of 6 the same as? And 7?

(e)How many different arrangements of 5 numbers are there? How many reflections and rotations does a given arrangement have? So how many different circle arrangements of 5 numbers are there?

(f)Now try finding all the circle arrangements of 5 numbers, and check for the sums you decided in part (d).

Question 5: AMC10A 2012 Problem 20

(a)Let’s get oriented. Draw a random arrangement and perform the rotation. Now try and draw one that turns to black

(b)What is the minimum number of black squares in the original arrangement (before rotation) that can turn entirely black? Can you find one of these minimum arrangements?

(c)If you want to, you could try and find all the arrangements that turn black from here. That’s what I did! You’ll have to be systematic – and consider reflections and rotations carefully.

(d)If you didn’t fancy part (c), you should now at least draw a few arrangements that turn black – what has to be true about them? Consider the corners and edges.

(e)Let’s just consider the corner colourings and ignore the rest. What can you say about how corners must be coloured to turn entirely black? Now do the same for edges. And the centre square?

(f)For every corner arrangement that turns black, you have n edge arrangements to consider. How can you use this idea to solve this problem?