Look at this formula found by Euler: \(n^2 +n +41\). It has a remarkable property: for every integer number from \(1\) to \(21\) it always produces prime numbers. For example, for \(n=3\) it is \(53\), a prime. For \(n=20\) it is \(461\), also a prime, and for \(n=21\) it is \(503\), prime as well. Could it be that this formula produces a prime number for any natural \(n\)?
Denote by \(n!\) (called \(n\)-factorial) the following product \(n!=1\cdot 2\cdot 3\cdot 4\cdot...\cdot n\). Show that if \(n!+1\) is divisible by \(n+1\), then \(n+1\) must be prime. (It is also true that if \(n+1\) is prime, then \(n!+1\) is divisible by \(n+1\), but you don’t need to show that!)
a) In a canteen, every day a chef prepares three lunch options customers can choose from. He is not a very good chef, but he knows six meals he can prepare very well. Every day, he chooses three out of these six and offers them. The options are presented left to right and we consider a lunch different if the three options are in different order, even if they are the same. For how many days can the chef go on, without repeating himself?
b) The customers have seen through chef’s plot and they realized that the order of the options does not in fact matter – there are still the same three lunches to choose from. If the chef now wants every day to be different, for how many days can he prepare different three meals each day?
A magician has \(10\) ingredients used for brewing potions. Any \(6\) have to be combined in order for brewing to be successful. How many different potions can the magician brew?
We have a set of \(7\) letters: A, T, E, W, L, O and R. We are interested in the \(4\) letter “words” that you can build from these letters, using each one only once. How many such “words” are there? What if we only want to build “words” such that the letters used are in the alphabetical order, how many “words” can we make then?
All the example problems followed a similar theme. You had to find the number of ways you can choose some \(k\) out of \(n\) items, if the order of choosing does not matter. We by now know the procedure to do so: First, pretend the order matters and pick \(k\) items, one item after the other, in \(n, n-1, n-2, \dots, n-k+1\) ways. To obtain the total number of ways to do that, we need to multiply them: \(n \times (n-1) \times \dots \times (n-k+1)\). Then, ask ourselves in how many ways can we order the items that we have chosen? Well, in \(k!\) ways, the number of permutations. Since the order does not matter, we need to divide the number found before by \(k!\).
The total number of combinations (choosing \(k\) out of \(n\) objects) is \[n \times (n-1) \times \dots \times (n-k+1)\div k! = \frac{n!}{k! \times (n-k)!}\] It is an important formula, and is often denoted with a special symbol \(\binom{n}{k}\), read “n choose k”. When solving the problems below, you can use the formula, or if you do not want to, just work them out individually, just like the examples!
Six girls – Ashley, Betty, Cindy, Donna, Eve and Fiona are members of a school maths circle (in another school obviously). In how many ways can you pick 4 of them to participate in a baths battle against the RGS team?
John’s dad is setting the table for a family dinner. He has \(13\) plates, all in different sizes. He will pick \(5\) plates, and then the largest will be for himself, the second largest for his wife, the third largest for John’s sister Dorothy, the fourth largest for John and the smallest will be for John’s little brother Louie. In how many ways can John’s father set the table?
Rithika drew \(10\) points on the board in such a way that no \(3\) of them belong to one straight line. How many triangles can she draw with vertices in these points?
a) A florist has \(11\) different types of flowers in her shop. She was asked to make a bouquet with \(4\) different flowers. In how many ways can she do that?
b) What if she was asked to use exactly \(7\) types of flowers?
c) Knowing the answer to a), do you know how and why is the answer to b) related to it?
Tom’s dad built a 9 board-long fence, which Tom’s mother painted white. Tom, who has 3 different cans of paint – red, green and blue – would like to decorate the fence.
a) If he paints every second board (boards 2, 4, ...), in how many ways can he do it?
b) If he paints every second board, and if exactly one of the boards should be red, in how many ways can he do it?
c) If he paints every board, if exactly three boards should be red, and if the fence should be symmetrical, in how many ways can he do it?