Classic olympiad problem · Combinatorics
Prove that a set with n elements has exactly 2^n subsets.
Prove that a set with elements has exactly subsets.
This is a proof problem. The answer is an argument, not a number. The solution is deliberately not posted here: reading a solution you didn't fight for teaches almost nothing. On Lemma you attempt it cold, take one of the 2 progressive hints only when genuinely stuck, then compare your proof against a full walkthrough and mark yourself with the same rubric a competition coordinator would use.
Guides that use this problem
- How many practice problems should you do a day?The daily count is the wrong target. How to size a practice session from your miss rate and review time, and why a mixed set beats a bigger one.
- Constructive vs complementary counting: which one to reach forTwo ways to count the same set, and one question that tells you which is cheaper. The signals, the worked pair, and the trap where the obvious tell lies to you.
- Generating functions: turning a counting problem into a productGenerating functions explained as a method: one factor per constraint, multiply, read the coefficient. The dictionary, and how to extract by hand.
- How to get better at proofs when you can only computeComputation is not the wrong skill for proofs, it is an unfinished one. Five moves that turn arithmetic you can already do into an argument that holds.
Train it on Lemma
This problem sits in the Olympiad Set: 89 proof problems (real IMO problems and the classics) with progressive hints, full walkthroughs and marking rubrics. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your levelMore Combinatorics problems
- Ramsey, R(3,3)=6Classic (Ramsey, $R(3,3)=6$) · difficulty 4/6
- Mutilated chessboardClassic (mutilated chessboard) · difficulty 3/6
- Handshake lemmaClassic (handshake lemma) · difficulty 2/6
- All 89 problems →