Combinatoric Proofs

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) SS is a subset of 1,2,,100{1, 2, \ldots, 100} with the property that no two elements of SS differ by 99. What is the maximum number of elements that SS 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 11 or 1-1

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


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

  • AA has at least 22 elements

  • The elements of AA form an arithmetic progression

  • The arithmetic progression cannot be extended in either direction using elements of SS.

How many full subsets of SS are there?


5) On an 8×88 \times 8 chess board we place an Xon the bottom left corner. All other squares are blank. Any 3×13 \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, or

  • it 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 nn be a positive integer and let rr be an integer such that 1rn1 \leq r \leq n. Consider all the rr element subsets of the set 1,2,,n{1, 2, \ldots, n}. For each such rr element subset, consider its smallest member. Prove that the average of these smallest numbers equals n+1r+1\dfrac {n + 1}{r + 1}.

Note by Sharky Kesa
4 years, 10 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

3) Let there be n 1s and (30-n) -1s. So there sum would be n(30n)=2n30>8n>19n-(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 20 1s. The number of possible arrangements=(1110)+(112)\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 one 1.

Let n=21 now. Place 9 -1s. We cannot accomodate 21 1s as 10 places can accomodate atmost 20 1s (Given 1st condition)

So n cannot be increased further.

So total number of ways=(1110)+(112)=11+55=66\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λ2\lambda and 2λ12\lambda-1

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

.

.

.

.

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

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

So total full sets when n is even will be 1+2+...+n2=n2×(n2+1)21+2+...+\frac{n}{2}=\boxed{\frac{\frac{n}{2}×(\frac{n}{2}+1)}{2}} and when n is odd will be 1+2+...+n12=n12×(n12+1)2 1+2+...+\frac{n-1}{2}=\boxed{\frac{\frac{n-1}{2}×(\frac{n-1}{2}+1)}{2}}

Pranjal Jain - 4 years, 10 months ago

Log in to reply

You got 1) wrong. I can make one with plenty more elements:

1,2,3,4,5,6,7,8,9,19,20,21,22,23,24,25,26,27,...{1, 2, 3, 4, 5, 6, 7, 8,9, 19, 20, 21, 22, 23, 24, 25, 26, 27,...}

Sharky Kesa - 4 years, 10 months ago

Log in to reply

Oh! Yeah! Difference of λ1\lambda_{1} and λ2\lambda_{2} can be 2!!! My bad! Lemme try it again!

Pranjal Jain - 4 years, 10 months ago

Log in to reply

@Pranjal Jain I guess one of the largest sets must be

{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λ+r19\lambda+r_{1} then 9(λ+1)+r19(\lambda+1)+r_{1} must not appear. I varied r from 0 to 8 taking λ=0\lambda=0 then I skipped λ=1\lambda=1 and so on...

Pranjal Jain - 4 years, 10 months ago

Log in to reply

2) Where did Irene come from?

Joel Tan - 4 years, 10 months ago

Log in to reply

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

Sharky Kesa - 4 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...