In this module, we’d discuss a couple of counting strategies that maybe useful while solving problems related to the Olympiads. We’d illustrate these strategies with the help of examples.
Ex-1) Let \(m,n\) be integers greater than 1. Consider \(S\) to be a set with \(n\) elements, and let \(A_1,A_2,..,A_m\) be subsets of \(S\). Assume that for any 2 elements \(x,y\in S\), there is a set \(A_i\) such that at least 1 of \(x,y\in A_i\), but not both of them. Show that \(n\le 2^m\).
Solution:
Let’s assign, to each element of \(S\), a sequence of \(m\) binary numbers. Thus, for all \(x\in S\), define \(\sigma(x)=(x_1,z_2,…,x_m)\), with \(x_i=0\) or \(1\) depending if \(x\not\in S\) or if \(x\in S\). Thus, we have defined a function \(f:S\rightarrow T=\{(x_1,x_2,..x_m)|x_i\in\{0,1\}\}\). Note that \(T\) . will definitely have at least as many elements as \(S\) has. Also \(|T|=2^m\Rightarrow n\le 2^m\).
The important strategy that we discussed over here is:
To solve an inequality related to counting problems, we might be able to map the required counting to a specific set of values in some domain, which is easier to count. This mapping can be injective (as, in this case), bijective or surjective. Importantly, choose a mapping where it’s easy to calculate the cardinality of the set of values to equate with the original problem.
Ex -2) An even number of persons are seated around a table. After a break, they’re again seated around the same table, not necessarily around the same places. Show that at least 2 of these persons have the same number of persons sitting between them as before the break.
Solution:
Let’s consider the problem statement in strict mathematical terms.
Let the seats be numbered from 1 to 2n. Thus, we need to show that there exists at least 1 \(i,j\) such that \(|i-j|=|\sigma(i)-\sigma(j)|\), where \(\sigma(i)\) denotes the position of the ith person after the break.
Consider that the 2n numbers were vertices of a regular Polygon, \(P_0,P_1,…,P_{2n-1}\). A rearrangement sends \(P_i\) to \(P_{\sigma(i)}\). Now, the number of vertices between \(P_a\) and \(P_b\) is the same after the permutation \(sigma\) if \(\sigma(a)-\sigma(b)\) and \(a-b\) leave the same remainder upon division by \(n\).
Suppose that by contradiction that this isn’t the case for any \(a,b\). Then we know that \(i-\sigma(i)\) leaves remainders 0,1,2,…,2n-1 modulo 2n.
Adding up these we have \(\sum i-\sum\sigma(i)\) leaves a remainder \(n(2n-1)\) when divided by \(2n\).
Note that \(\sum i=\sum\sigma(i)\), and \(n(2n-1)\) is never divisible by \(2n\), thus contradicting our assumptions.
The important strategy discussed over here is
Try to construct a model where we can use some mathematical tools to prove our newly modelled statement.