2018 UNCO Math Contest II Problems/Problem 9

Problem

Call a set of integers Grassilian if each of its elements is at least as large as the number of elements in the set. For example, the three-element set $\{2, 48, 100\}$ is not Grassilian, but the six-element set $\{6, 10, 11, 20, 33, 39\}$ is Grassilian. Let $G(n)$ be the number of Grassilian subsets of $\{1, 2, 3, ..., n\}$ . (By definition, the empty set is a subset of every set and is Grassilian.)

(a) Find $G(3)$ , $G(4)$ , and $G(5)$ .

(b) Find a recursion formula for $G(n + 1)$ . That is, find a formula that expresses $G(n + 1)$ in terms of $G(n), G(n - 1),\dots$

(c) Give an explanation that shows that the formula you give is correct.

Solution

a) $G(3) = 5, G(4) = 8, G(5) = 13$

b) $G(n) = G(n - 1) + G(n - 2); G(0) = 1 \text{ and } G(1) = 2$

c) $G(n + 1) = G(n) + G(n - 1)$ .

2018 UNCO Math Contest II (Problems • Answer Key • Resources)
Preceded by Problem 8	Followed by Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNCO Math Contest Problems and Solutions

Page

Toolbox

Search

2018 UNCO Math Contest II Problems/Problem 9

Problem

Solution

See also