For teachers / Printable sets /Stage 4 · Combinatorics

Stage 4 · Combinatorics

10 problems · AMC 12 late, AIME early · mathsolympiadprep.com

Print or save as PDF The answer key prints on its own page at the end.

1. How many diagonals does a regular undecagon (11-sided polygon) have?

   Annual Harvard-MIT November Tournament

   Combinatorics Solution and answer checking →

2. From the set $\{1,2, \ldots, 100\}$ we choose 50 distinct numbers, whose sum is 3000. At minimum, how many even numbers have we chosen?

   1. A2
   2. B3
   3. C4
   4. D5
   5. E6

   Olimpiadi di Matematica

   Combinatorics Solution and answer checking →

3. How many ordered pairs $(A, B)$ of subsets of $\{1,2,3,4,5\}$ are there such that the intersection of $A$ and $B$ has exactly one element?

   1. A80
   2. B280
   3. C1280
   4. D751
   5. E405

   Progetto Olimpiadi della Matematica

   Combinatorics Solution and answer checking →

4. Suppose set $S = \{1, 2, 3, \dots, 10\}$ and the subset $A$ of $S$ satisfies

   $$A \cap \{1, 2, 3\} \neq \emptyset, \quad A \cup \{4, 5, 6\} \neq S.$$
   The number of such subsets is ________.

   China Mathematical Competition

   Combinatorics Solution and answer checking →

5. A computer program is a function that takes in 4 bits, where each bit is either a $0$ or a $1$, and outputs TRUE or FALSE. How many computer programs are there?

   Harvard-MIT November Tournament

   Combinatorics Solution and answer checking →

6. Compute the smallest positive integer that does not appear in any problem statement on any round at HMMT November 2023.

   HMMT November

   Combinatorics Solution and answer checking →

7. There is a $6 \times 6$ grid of lights. There is a switch at the top of each column and on the left of each row. A light will only turn on if the switches corresponding to both its column and its row are in the "on" position. Compute the number of different configurations of lights.

   HMMT November 2023

   Combinatorics Solution and answer checking →

8. How many ways can the eight vertices of a three-dimensional cube be colored red and blue such that no two points connected by an edge are both red? Rotations and reflections of a given coloring are considered distinct.

   HMMT November 2014

   Combinatorics Solution and answer checking →

9. The 60 inhabitants of a village can be of three types: farmers (who always tell the truth), werewolves (who always lie) and necromancers (who answer as they wish). Except for these behaviors, the members of each faction are completely indistinguishable from those of the others. Upon the arrival of a visitor they arrange themselves in a circle and each one declares that the inhabitant to his right is a werewolf. Which of these statements is necessarily true?

   1. AThere is at least one necromancer
   2. BThe werewolves are at most 20
   3. CThe farmers are at most 30
   4. DThe necromancers are no more than 40
   5. ENone of the above

   Progetto Olimpiadi della Matematica - GARA di FEBBRAIO

   Combinatorics Solution and answer checking →

10. 10 people are playing musical chairs with $n$ chairs in a circle. They can be seated in $7!$ ways (assuming only one person fits on each chair, of course), where different arrangements of the same people on chairs, even rotations, are considered different. Find $n$.

    Harvard-MIT Mathematics Tournament

    Combinatorics Solution and answer checking →

Answer key — Stage 4 · Combinatorics

Worked solutions for every problem are on the site, one page per problem.

1. $44$ open
2. $E$ open
3. $E$ open
4. $888$ open
5. $65536$ open
6. $22$ open
7. $3970$ open
8. $35$ open
9. $C$ open
10. $4$ open

Problems belong to the competitions that set them. Each question on this sheet names the competition it came from, and the licences the material is used under are listed below. Free to copy for classroom use.

CC-BY-4.0 · Apache-2.0