Difference between revisions of "2018 UNCO Math Contest II Problems/Problem 9"

m (Problem)
m (Solution)
 
Line 17: Line 17:
 
b) <math>G(n) = G(n - 1) + G(n - 2); G(0) = 1 \text{ and } G(1) = 2</math>
 
b) <math>G(n) = G(n - 1) + G(n - 2); G(0) = 1 \text{ and } G(1) = 2</math>
  
c) <math>G(n + 1) = G(n) + G(n 1)</math>.
+
c) <math>G(n + 1) = G(n) + G(n - 1)</math>.
  
 
== See also ==
 
== See also ==

Latest revision as of 20:02, 28 October 2023

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)$.

See also

2018 UNCO Math Contest II (ProblemsAnswer KeyResources)
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