This is an optional module for students preparing for the engineering entrance exams.
Q-1) Among 6 persons in a room, there are either 3 who know each other or 3 who are complete strangers
Solution :
Let us consider a hexagon with each person denoting a specific vertex of the hexagon. We join 2 vertices with a green line if the 2 people represented by these vertices know each other, else we join them by a red line if they’re strangers. Let’s pick any vertex and call it P. Out of the 5 lines emanating from P, at least 3 of them must be of the same colour (assume green). Let the vertices to which these 3 lines connect P with be A,B,C. If any of the sides of \(\triangle ABC\) is green, we have a green triangle. If not, then ABC is a red triangle, but in any case it’s a triangle all of whose 3 sides are of the same colour, thus proving our statement.
We generalise this to the following statement:
In space, there are \(p_n = \left \lfloor en! \right \rfloor+1\) points. If each pair of points is connected by a line, and each line is covered by one of n colours, then there is at least one triangle with sides of the same colour.
This is called Ramsey’s Theorem.
Q-2) Let \(a_1,a_2,…a_n\) be a set of \(n\) not necessarily distinct integers. Show that there exists a subset of this set whose sum is divisible by \(n\).
Solution:
Consider the following sums:
\(s_1=a_1\), and in general \(s_k=\sum\limits_{i=1}^{k}a_i\) with \(1\le k \le n\). With these \(n\) sums, if any of them is divisible by \(n\), then we are done. Thus, assuming none of these sums have 0 remainder when divided by \(n\), we have \(n\) sums and \((n-1)\) distinct remainders when these sums are divided by \(n\). Thus some 2 sums have the same remainder when they’re divided by \(n\). If we subtract those 2 sums, we have a subset whose sum will leave 0 remainder when divided by \(n\).
Q-3) Let’s say that we need to colour all the sides of a cube by a distinct colour (We have 6 different colours). How many distinct colourings can be possible?
Solution:
If it were not for the symmetry of the cube there would have been 6!=720 possible ways to colour the cube.
So, let’s keep the cube on a table, and colour the cube with the side facing the table, i.e the base of the cube in 1 colour. Next, we have 5 possible choices to colout the side facing us. The remaining sides can be coloured in 3!=6 ways. Thus the total number of colourings possible = \(5\times 3!=30\).
Q-4) Let \(B_m=\{1,2,3…,m\}\) and \(B_n=\{1,2,3,…,n\}\) with \(m\ge n\). We define a mapping from \(B_m\) onto \(B_n\) as a surjection, if all elements of \(B_n\) are mapped to at least 1 element of \(B_m\), however no element of \(B_m\) is mapped to 2 elements of \(B_n\). Find the number of such surjections.
Solution:
The key is to use PIE (Principle of Inclusion and Exclusion) over here.
If we denote by \(A_i\), the number of mappings in which the ith element of \(B_n\) is not mapped to any element of \(B_m\), then we have
If we subtract this number from \(n^m\), or the set of all mappings, we will have the number of surjections \(s(m,n)\).
Q-5) Catalan Numbers: We define the nth Catalan Number by the formula \(C_n=\frac{1}{n+1}C(2n,n)\). Catalan Numbers have a wide range of applications in Combinatorics. the applications can be read about over here in the Wiki Page itself. One of the applications involve the number of ways to reach the point (n,n) from (0,0) by taking either 1 step to the right or one step in the upward direction. But you shouldn’t ever be crossing the line \(y=x\). The number of such paths (often referred to as good paths) turns out to be the nth Catalan Number. Often, we draw a bijection between a problem statement with the problem of Catalan numbers. In these cases, it’s often helps with the notion of the nth Catalan number.
2n points are chosen on a circle. In how many ways can you join pairs of points by non-intersecting chords?
Solution:
Let’s consider the above figure and mark our chords in the following way:
Go around the circle in any way, meeting a diagonal for the first time, we label it as ‘b‘, else if we’re meeting it for the second time we label it as ‘e‘. COnsidering the scenario for non-intersecting chords, we get the word bbbeebbbeeee… . If we consider b as a step to the right, and e as a step in the upward direction, then this can be considered to be a ‘good path’ as described above. This enables us to draw a bijection between good paths and the words that we form following the logic that we described above. And hence the number of ways is simply the nth Catalan Number.
Q-6) Consider a row of n seats, with a person sitting on each sit. Each person can move by at most 1 seat. Find the number of seating arrangements.
Solution:
Let’s denote the number of rearrangements by \(a_n\). If we fix the first person, then we have \(a_{n-1}\) rearrangements. Now if the first person moves to 2, then the second person must move back to 1, in which case we get \(a_{n-2}\) arrangements. Thus we have \(a_n=a_{n-1}+a_{n-2}\). We have \(a_1=1\), \(a_2=2\), thus \(a_n=F_{n+1}\), where \(F_n\) is the nth Fibonacci number.
Q-7) Let \(1\le r\le n\), and consider all r-element subsets of the set \(\{1,2…,n\}\). Show that the average of the smallest number of each of these r-element subsets is \(F(n,r)=\frac{n+1}{r+1}\).
Solution:
We have exactly \(C(n,r)\) r-element subsets of the given set. Thus the total sum of these subsets is \(F(n,r)\times C(n,r)\). Now, let’s try to map an (r+1) element subset with an r-element subset. If we strip off the least element of this (r+1) element set, we will get an eventual r-element subset. However, this r-element set shall occur exactly i number of times where i is the least element of that set. We can thus say
\(C(n+1,r+1)=C(n,r)F(n,r)\Rightarrow F(n,r)=\frac{C(n+1,r+1)}{C(n,r)}=\frac{n+1}{r+1} \).
Q-8) All the points in the 3 sides of an equilateral triangle are coloured by 1 of 2 colours. Show that there exists 3 points of the same colour such that they form the vertices of a right angled triangle
Solution:
Assume that there’s no such right angled triangle with vertices of the same colour. We partition each side of the triangle into 3 equal parts by 2 points. These 6 points across the 3 sides of the triangle form the vertices of a regular hexagon. If 2 of the opposite vertices are of the same colour, then all other vertices are of the other colour, in which case, we’ll get a right angled triangle with vertices of the same colour. Thus, the opposite vertices must belong to different colours, implying that there exists 2 neighbouring vertices of different colours. Thus, one pair of these bicoloured vertices lie on a side of the given triangle. The points of this side, differing from the vertices of the hexagon cannot thus belong to either of the 2 colours – a contradiction!
Q-9) Let n be a positive integer not divisible by 2 or 5. Show that there exists a multiple of n consisting entirely of 1’s.
Solution:
Consider the numbers 1,11,111,1111,…. – n of them. If we consider the remainders modulo n, there’ll be exactly n of them. If we have 0, we are done, else there’ll be (n-1) distinct remainders. Thus, 2 numbers have the same remainder, implying their difference – 111…0000 will be divisible by n. But since n is not divisible by 2 0r 5, the number 1111…1, stripping of the trailing zeros is divisible by n.
Q-10) Show that from a set of 10 distinct 2 digit numbers, one can always choose 2 disjoint subsets which have the same sum.
Solution:
We can form a total of \(2^{10}=1024\) subsets from these 10 numbers. The number of sums possible \(\le 10\times 99 =990\), which trivially implies that not all subsets will have distinct sums. In case, we have a few common elements in these subsets, we can remove them from both the sets and still be left with 2 subsets, that are disjoint and share the same sum.