Question
In how many subsets of {1,2,3,4,…n} is the sum of the largest element and the smallest element equal to (n+1)?
Solution
I am able to deduce the following:
- If the smallest element is 1, then the largest element has to be n. The rest of the n−2 elements can be "in" or "out", thus the total will be 2n−2
- Similarly, If the smallest element is 2, then the largest element has to be n−1. And again, it will have 2n−4 such subsets
- ……
Final Answer
- If n is odd the total subsets will be: 2n−2+2n−4+…+21
- If n is even the total subsets will be: 2n−2+2n−4+…+20
#Combinatorics
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Can anyone suggest a cleaner and short-hand form for the above answer?
Log in to reply
This is good. Nothing to improve on.
Log in to reply
Ok.
The best answer possible is given. You can also write it as: ∑n≥k≥2:2∣k2n−k
Log in to reply
Hmm.. it is pretty compact but could be hard to understand. Thanks though!
Pretty good!
Log in to reply
Thanks!
Log in to reply
No problem!
I had a thought:
For any integer x and any prime p, can
px
always be irreducible if x isn't a factor of p?
Make a note on it if you have proof.
Log in to reply
Log in to reply
Let px=k where 'k' is an integer.
For k to be an integer, x=pk
That means x has to obviously be a multiple of p.
Log in to reply
@Hamza Anushath?
Great! You did see my comment to