In this note, I have a selection of questions for you to prove. It is for all levels to try. The theme is combinatorics. Good luck.

1) \(S\) is a subset of \({1, 2, \ldots, 100}\) with the property that no two elements of \(S\) differ by \(9\). What is the maximum number of elements that \(S\) can have?

2) Brilli the Ant and Brian Till play a game by taking turns removing some stones from a pile. The number of stones removed at each turn must be a divisor of the number of stones in the pile at the start of that turn, and no player is ever allowed to take all the stones in the pile. The person who cannot move is the loser.

If they start with 2008 stones and Brilli goes first, who has the winning strategy?

3) How many sequences of 30 terms are there, such that the following three conditions are satisfied:

no sequence has three consecutive terms equal to each other

every term of the sequence is equal to \(1\) or \(-1\)

the sum of all terms of each sequence is greater than 8?

4) Let \(S = {1, 2, \ldots, n}\), where \(n\) is a positive integer greater than or equal to \(2\). A subset \(A\) is *full* if it has the following three properties:

\(A\) has at least \(2\) elements

The elements of \(A\) form an arithmetic progression

The arithmetic progression cannot be extended in either direction using elements of \(S\).

How many *full* subsets of \(S\) are there?

5) On an \(8 \times 8\) chess board we place an **X**on the bottom left corner. All other squares are blank. Any \(3 \times 1\) row or column of squares is called a *playable set* if either

it contains exactly two squares with an

**X**in each, one of which must be the middle square of the playable set, orit contains exactly two blank squares, one of which must be the middle square of the playable set.

At any stage it is permitted to choose any playable set and simultaneously change every **X** into a blank, and every blank into a square with an **X**. After a finite number of such changes, Brilli has reached a configuration with exactly one square containing an **X**. Which square or squares could it be?

6) Let \(n\) be a positive integer and let \(r\) be an integer such that \(1 \leq r \leq n\). Consider all the \(r\) element subsets of the set \({1, 2, \ldots, n}\). For each such \(r\) element subset, consider its smallest member. Prove that the average of these smallest numbers equals \(\dfrac {n + 1}{r + 1}\).

## Comments

Sort by:

TopNewest2) Where did Irene come from? – Joel Tan · 2 years, 1 month ago

Log in to reply

– Sharky Kesa · 2 years, 1 month ago

Sorry, I was thinking about other character names. Forgot I had put that name. Brilli was originally Irene. I changed the name.Log in to reply

3)Let there be n1s and (30-n)-1s. So there sum would be \(n-(30-n)=2n-30>8 \Rightarrow n>19\)Now let n=20, so that number of

1s=20 and number of-1s=10. Now first place all-1s. We have 11 places (9 between two-1s and 2 ends) to put up 201s. The number of possible arrangements=\(\binom{11}{10}+\binom{11}{2}\). First one is when one out of 11 places is empty and second when two out of 11 places have one1.Let n=21 now. Place 9

-1s. We cannot accomodate 211s as 10 places can accomodate atmost 201s (Given 1st condition)So n cannot be increased further.

So total number of ways=\(\binom{11}{10}+\binom{11}{2}=11+55=\boxed{66}\)

4)Lets analyze the problem with different common differences starting with 1.(i) common difference=1, full set={1,2,3,4,...,n}

(ii) common difference=2, 2 full sets with general term \(2\lambda\) and \(2\lambda-1\)

(iii) common difference=3, 3 full sets with general term \(3\lambda\), \(3\lambda+1\) and \(3\lambda+2\)

.

.

.

.

common difference=\(\frac{n}{2}\), \(\frac{n}{2}\) full sets (For even n)

common difference=\(\frac{n-1}{2}\), \(\frac{n-1}{2}\) full sets (For odd n)

So total full sets when n is even will be \(1+2+...+\frac{n}{2}=\boxed{\frac{\frac{n}{2}×(\frac{n}{2}+1)}{2}}\) and when n is odd will be \( 1+2+...+\frac{n-1}{2}=\boxed{\frac{\frac{n-1}{2}×(\frac{n-1}{2}+1)}{2}}\) – Pranjal Jain · 2 years, 1 month ago

Log in to reply

\({1, 2, 3, 4, 5, 6, 7, 8,9, 19, 20, 21, 22, 23, 24, 25, 26, 27,...}\) – Sharky Kesa · 2 years, 1 month ago

Log in to reply

– Pranjal Jain · 2 years, 1 month ago

Oh! Yeah! Difference of \(\lambda_{1}\) and \(\lambda_{2}\) can be 2!!! My bad! Lemme try it again!Log in to reply

{1,2,3,4,5,6,7,8,9, 19,20,21,22,23,24,25,26,27, 37,38,39,40,41,42,43,44,45, 55,56,57,58,59,60,61,62,63, 73,74,75,76,77,78,79,80,81, 91,92,93,94,95,96,97,98,99} having 54 elements!

I just used the fact that if a number is \(9\lambda+r_{1}\) then \(9(\lambda+1)+r_{1}\) must not appear. I varied r from 0 to 8 taking \(\lambda=0\) then I skipped \(\lambda=1\) and so on... – Pranjal Jain · 2 years, 1 month ago

Log in to reply