Sometimes one can guess certain multiples of a number just by looking at it, the idea of this sheet is to learn to recognise quickly using tricks when a natural number is divisible by another number.
Today we’re going to learn a simple idea from a branch of math called combinatorics, which is all about clever ways to count things. The idea we’re learning is called the Product Rule.
The Product Rule says this: if you need to do two actions in a row, and the first action can be done in, say, \(5\) different ways, and for each of those choices the second action can be done in \(4\) different ways, then the total number of possible outcomes is \(5 \times 4\).
Why? Because every choice for the first action opens up all the possible choices for the second action. So each of the \(5\) first choices has \(4\) second choices that can follow it. Let’s see in a few examples this idea in practice:
On a chessboard (an \(8 \times 8\) grid), we place eight identical rooks. A rook can move any number of squares in a straight line horizontally (along a row) or vertically (along a column). In chess, a piece can take another piece if it can move to the other piece’s square in a single move.
In how many ways can we arrange the eight rooks so that no rook can take any other?
How many five-digit numbers are there which are written the same from left to right and from right to left? For example the numbers \(54345\) and \(12321\) satisfy the condition, but the numbers \(23423\) and \(56789\) do not.
A set is a collection of elements where each element appears only once. The elements are not ordered, and there is no rule connecting them. Even a set with no elements (an empty set) counts as a set. The collections \(\{a,b,c,d\}\) and \(\{3,2,45,1,0,\pi\}\) are both examples of sets.
Let \(C\) be a set with \(n\) elements. How many different sets can be formed using the elements of \(C\)?
There are six letters in the alphabet of the Gloops. A word is any sequence of six letters that has at least two identical letters. How many words are there in the language of the Gloops?
Each cell of a \(3 \times 3\) square can be painted either black, white, or grey. How many different ways are there to colour in this table?
Consider a set of numbers \(\{1,2,3,4,...n\}\) for natural \(n\). Find the number of permutations of this set, namely the number of possible sequences \((a_1,a_2,...a_n)\) where \(a_i\) are different numbers from \(1\) to \(n\).
A rectangular parallelepiped of the size \(m\times n\times k\) is divided into unit cubes. How many rectangular parallelepipeds are formed in total (including the original one)?
In the Land of Linguists live \(m\) people, who have opportunity to speak \(n\) languages. Each person knows exactly three languages, and the sets of known languages may be different for different people. It is known that \(k\) is the maximum number of people, any two of whom can talk without interpreters. It turned out that \(11n \leq k \leq m/2\). Prove that then there are at least \(mn\) pairs of people in the country who will not be able to talk without interpreters.