Consider the collection of all three-element subsets drawn from the set 1 , 2 , 3 , 4 , … , 299 , 300 . Determine the number of these subsets for which the sum of the three elements is a multiple of 3 .

We have, S = 1 , 2 , 3 , 4 , … , 299 , 300 For 0 ≤ j ≤ 2 , let A j denote the set of all integers between 1 and 300 which leave remainder j when divided by 3 . Then A j = 100 for 0 ≤ j ≤ 2 . If a , b , c is a 3 -element subset of the given set S , then 3 divides a + b + c if and only if i All a , b , c are in A 0 or in A 1 or in A 2 . ii One of the a , b , c is in A 0 , another in A 1 , and the third one in A 2 . The number of 3 -element subsets of A j , 0 ≤ j ≤ 2 is C 3 100 = 161700 . For each choice of a in A 0 , b in A 1 and c in A 2 , we get a 3 -element subset such that 3 | a + b + c . Thus, the total number of 3 -element subsets a , b , c such 3 divides a + b + c is equal to = 3 × C 3 100 + 100 3 = 1485100

Consider the collection of all three-element subsets drawn from the set 1 , 2 , 3 , 4 , … , 299 , 300 . Determine the number of these subsets for which the sum of the three elements is a multiple of 3 .

We have, S = 1 , 2 , 3 , 4 , … , 299 , 300 For 0 ≤ j ≤ 2 , let A j denote the set of all integers between 1 and 300 which leave remainder j when divided by 3 . Then A j = 100 for 0 ≤ j ≤ 2 . If a , b , c is a 3 -element subset of the given set S , then 3 divides a + b + c if and only if i All a , b , c are in A 0 or in A 1 or in A 2 . ii One of the a , b , c is in A 0 , another in A 1 , and the third one in A 2 . The number of 3 -element subsets of A j , 0 ≤ j ≤ 2 is C 3 100 = 161700 . For each choice of a in A 0 , b in A 1 and c in A 2 , we get a 3 -element subset such that 3 | a + b + c . Thus, the total number of 3 -element subsets a , b , c such 3 divides a + b + c is equal to = 3 × C 3 100 + 100 3 = 1485100

How many 3 -element subsets of the set 1 , 2 , 3 , … , 19 , 20 are there such that the product of the three numbers in the subset is divisible by 4 ?

Let S = 1 , 2 , 3 , … , 19 , 20 Total number of subsets of set S = 2 20 . We count the 3 -element subsets a , b , c such that 4 does not divide a b c . This is possible if and only if either all the three are odd numbers or any two of them are odd and the other is an even number not divisible by 4 . There are 10 odd numbers in the set S and 5 even numbers not divisible by 4 which are 2 , 6 , 10 , 14 , 18 . Thus, the number of 3 -element subsets a , b , c such that 4 does not divide a b c is equal to = C 3 10 + 5 × C 2 10 = 345 The number of 3 -element subsets of a set S is = C 3 20 = 1140 Thus, the number of 3 -element subsets such that the product of these elements is divisible by 4 is equal to = 1140 - 345 = 795

Suppose A 1 , A 2 , … , A 6 are six sets each with four elements and B 1 , B 2 , … , B n are n sets each with two elements such that A 1 ∪ A 2 ∪ ⋯ ∪ A 6 = B 1 ∪ B 2 ∪ ⋯ ∪ B n = S (say) Given that each element of S belongs to exactly four of the A i 's and exactly three of the B j 's, find n .

Since each A i contains 4 elements, totally we get 24 elements of which some may be repeated. But each element is repeated 4 times as each element belongs to exactly 4 of the A i ' s . Hence, there are 24 4 = 6 distinct elements in S . Since. S = B 1 ∪ B 2 ∪ B 3 ∪ ⋯ ∪ B n , and each B i consists of 2 elements, this union accounts for 2 n elements. But each element appears exactly 3 times. Thus, the number of distinct elements in S is also equal to 2 n 3 . Therefore, 2 n 3 = 6 ⇒ n = 9

Find the number of permutations, P 1 , P 2 , … , P 6 , of 1 , 2 , … , 6 such that for any k , 1 ≤ k ≤ 5 , P 1 , P 2 , … , P k does not form a permutation of 1 , 2 , … , k . [That is, P 1 ≠ 1 ; P 1 , P 2 is not a permutation of 1 , 2 , etc.

We shall look at the problem from a general viewpoint. For any positive integer n , let T n denote the number of permutations P 1 , P 2 , P 3 , … , P n of 1 , 2 , 3 , … , n such that for each k , 1 ≤ k ≤ n - 1 , P 1 , P 2 , P 3 , … , P k is not a permutation of 1 , 2 , … , k . We shall obtain a formula for T n which expresses T n in terms of T 1 , T 2 , . . . . . . , T n - 1 n > 1 (Such a relation is called a recurrence relation for T n .) Consider any permutation P 1 , P 2 , P 3 , … , P n of 1 , 2 , … , n . There is always at least positive integer k such that P 1 , P 2 , P 3 , … P k is a permutation of 1 , 2 , … , k . In fact k may be any integer in the set 1 , 2 , … , n ; and those permutations for which k = n are exactly the ones we wish to count. The number of permutations of 1 , 2 , … , n for all of which k is the least positive integer satisfying the above property is T k · n - k ! , by our definition of T n . The second factor corresponds to the permutations of k + 1 , k + 2 , … , n which fill up the remaining n - k places. Since there are n ! permutations in all, we obtain n ! = ∑ k = 1 n T k · n - k ! ⇒ n ! = T 1 · n - 1 ! + T 2 · n - 2 ! + ⋯ + T n - 1 · 1 ! + T n · 0 ! ⇒ T n = n ! - T 1 · n - 1 ! - T 2 · n - 2 ! - . . . . - T n - 1 · 1 ! Clearly, T 1 = 1 T 2 = 2 ! - T 1 · 1 ! = 2 - 1 = 1 T 3 = 3 ! - T 1 · 2 ! - T 2 · 1 ! = 6 - 2 - 1 = 3 T 4 = 4 ! - T 1 · 3 ! - T 2 · 2 ! - T 3 · 1 ! = 24 - 6 - 2 - 3 = 13 T 5 = 5 ! - T 1 · 4 ! - T 2 · 3 ! - T 3 · 2 ! - T 4 · 1 ! = 120 - 24 - 6 - 6 - 13 = 71 T 6 = 6 ! - T 1 · 5 ! - T 2 · 4 ! - T 3 · 3 ! - T 4 · 2 ! - T 5 · 1 ! = 720 - 120 - 24 - 18 - 26 - 71 = 461 Thus, the required number is 461 .

HARD

Olympiad

IMPORTANT

Earn 100

Consider the collection of all three-element subsets drawn from the set $\{1, 2, 3, 4, \dots, 299, 300\}$ . Determine the number of these subsets for which the sum of the three elements is a multiple of $3$ .

Important Questions on Combinatorics

HARD

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 77

How many

3

-element subsets of the set

\{1, 2, 3, \dots, 19, 20\}

are there such that the product of the three numbers in the subset is divisible by

4

MEDIUM

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 78

Suppose $A_{1}, A_{2}, \dots, A_{6}$ are six sets each with four elements and $B_{1}, B_{2}, \dots, B_{n}$ are $n$ sets each with two elements such that

$A_{1} \cup A_{2} \cup \dots \cup A_{6} = B_{1} \cup B_{2} \cup \dots \cup B_{n} = S$ (say)

Given that each element of $S$ belongs to exactly four of the $A_{i}$ 's and exactly three of the $B_{j}$ 's, find $n$ .

HARD

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 79

Two boxes contains

65

balls of several different sizes. Each ball is white, black, red, or yellow. If you take any five balls of the same colour, at least two of them will always be of the same size (radius). Prove that there are at least three balls which lie in the same box, have the same colour and are of the same size.

MEDIUM

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 80

There are two urns each containing an arbitrary number of balls. Both are non-empty to begin with. We are allowed two types of operations:

$(a)$ Remove an equal number of balls simultaneously from both urns.

$(b)$ Double the number of balls in any one them.

Show that after performing these operations finitely many times, both the urns can be made empty.

HARD

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 81

Let

A

denote a subset of the set

\{1, 11, 21, 31, \dots 541, 551\}

having the property that no two elements of

A

add upto

552

. Prove that

A

cannot have more than

28

elements.

HARD

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 82

Let

A = \{1, 2, 3, \dots 100\}

and

B

a subset of

A

having

48

elements. Show that

B

has two distinct elements

x

and

y

whose sum is divisible by

11

HARD

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 83

Find the number of permutations,

(P_{1}, P_{2}, \dots, P_{6})

, of

(1, 2, \dots, 6)

such that for any

k, 1 \leq k \leq 5, (P_{1}, P_{2}, \dots, P_{k})

does not form a permutation of

1, 2, \dots, k

.
[That is,

P_{1} \neq 1; (P_{1}, P_{2})

is not a permutation of

1, 2

, etc.

HARD

Olympiad

IMPORTANT

Problem Primer for the Olympiad>Chapter 4 - Combinatorics>Combinatorics>Q 84

There are seventeen distinct positive integers such that none of them has a prime factor exceeding

10

. Show that the product of some two of them is a square.

Consider the collection of all three-element subsets drawn from the set 1,2,3,4,…,299,300. Determine the number of these subsets for which the sum of the three elements is a multiple of 3.

Important Questions on Combinatorics

Learn and Prepare for any exam you want !

Consider the collection of all three-element subsets drawn from the set $\{1, 2, 3, 4, \dots, 299, 300\}$ . Determine the number of these subsets for which the sum of the three elements is a multiple of $3$ .