MathDB

2013 MTRP Senior

Part of Mathematics Talent Reward Programme (MTRP)

Subcontests

(8)
8
1
7
1
6
1

MTRP 2013 Senior Paper Question 6

Let N = {1, 2, . . . , n} be a set of elements called voters. Let C = {S : S ⊆\subseteq N} be the power set of N. Members of C are called coalitions. Let f be a function from C to {0, 1}. A coalition S ⊆\subseteq N is said to be winning if f(S) = 1; it is said to be losing if f(S) = 0. Such a function is called a voting game if the following conditions hold: (a) N is a wining coalition. (b) The empty set Φ\Phi is a losing coalition. (c) If S is a winning coalition and S ⊆\subseteq S' is also winning. (d) If both S and S' are winning then S ∩\cap S' ≠\neq Φ\Phi, i.e S and S' have a common voter. Show that the maximum number of winning coalitions of a voting game is 2n−12^{n-1}. Also find such a voting game.
5
1
4
1
3
1
2
1

MTRP 2013 Senior Paper Question 2

There are 1000 doors D1,D2,...,D1000D_1, D_2, . . . , D_{1000} and 1000 persons P1,P2,...,P1000P_1, P_2, . . . , P_{1000}. Initially all the doors were closed. Person P1P_1 goes and opens all the doors. Then person P2P_2 closes door D2,D4,...,D1000D_2, D_4, . . . , D_{1000} and leaves the odd numbered doors open. Next P3P_3 changes the state of every third door, that is, D3,D6,...,D999D_3, D_6, . . . , D_{999} . (For instance, P3P_3 closes the open door D3D_3 and opens the closed door D6, and so on). Similarly, PmP_m changes the state of the the doors Dm,D2m,D3m,...,Dnm,...D_m, D_{2m}, D_{3m}, . . . , D_{nm}, . . . while leaving the other doors untouched. Finally, P1000P_{1000} opens D1000D_{1000} if it was closed or closes it if it were open. At the end, how many doors will remain open?
1
1