Practice (TheColoringMethod)

back to index  |  new

Let $\alpha(n)$ be the number of ways to write a positive integer $n$ as the sum of $1$s and $2$s. Let $\beta(n)$ be the number of ways to write $n$ as a sum of several integers greater than $1$. Different orders are treated as different. Prove $\alpha(n)=\beta(n+2)$.


A deck of poker has three different colors each of which contains $10$ cards numbered from $1$ to $10$, respectively. In addition, there are two jokers both of which are numbered as $0$. A card with number $k$ is valued as $2^k$ points. How many different ways are there to draw several cards from this deck so that their total value equals $2004$?


Compute the value of $$\sum_{k=0}^{n}\frac{1}{2^k}\binom{n+k}{n}$$


Let $n$ be a positive integer. Find the number $a_n$ of polynomials $f(x)$ with coefficients in $\{0, 1, 2, 3\}$ such that $f(2)=n$.


Let $a_0$, $a_1$, $a_2$, $\cdots$ be an increasing sequence of non-negative integers such that every non-negative integer can be expressed uniquely in the form of $(a_i + 2a_j+4a_k)$ where $i$, $j$, and $k$ are not necessarily distinct. Determine $a_{1998}$.


Let $\mathbb{N}$ be the set containing all positive integers. Is it possible to partition $\mathbb{N}$ to more than one but still a finite number of arithmetic sequences with no two having the same common difference?


Let $p$ be an odd prime number. Find the number of subsets $\mathbb{A}$ of the set $\{1, 2, \cdots, 2p\}$ such that $\mathbb{A}$ has exactly $p$ elements and the sum of all elements in $\mathbb{A}$ is divisible by $p$.


Let $a$, $b$, $p$, and $q$ be fixed positive integers. If an $a\times b$ grid can be tiled using some $1\times p$ and $q\times 1$ pieces, show that either $a$ is divisible by $p$ or $b$ is divisible by $q$. Here, a $1\times k$ and $k\times 1$ grids are treated as different.


Show that $$\frac{1}{1-ax}=\sum_{k=0}^{\infty}(ax)^n$$

Show that $$\frac{1}{1-x}=1+x+x^2+x^3+x^4 + \cdots$$


Show that $$\frac{1}{1+x}=\sum_{k=0}^{\infty}(-1)^nx^n$$


(right shifting) Find the generating function for the sequence: $$\underbrace{0, 0, \cdots, 0}_{k}, 1, 1, 1, 1, \cdots$$


Show that $$\frac{1}{1-x^2}=\sum_{k=0}^{\infty}x^{2k}$$


Show that $$\frac{1}{(1-ax)^n}=\sum_{k=0}^{\infty}a^k\binom{n-k}{n-1}x^k$$


Find the generating function for the sequence $1$, $2$, $3$, $4$, $\cdots$.


Find the generating function for the sequence $0$, $1$, $2$, $3$, $\cdots$.


Show that $$\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots$$


Find the generating function for the sequence $2,\ 3,\ 4,\ 5,\ \cdots$.


Find the number of subsets of $\{1,\ 2,\ ,3\ ,\cdots,\ 2021\}$ the sum of whose elements is divisible by $101$. (Empty subset is permitted).


Seven students took a math exam. Every problem was solved at at most $3$ students. For every pair of students, there is at least one problem which was solved by both of these two students. What is the minimal number of problem this exam contains?


A partition of a positive integer $n$ is to write $n$ as a sum of some positive integers. Let $k$ be a positive integer. Show that the number of partitions of $n$ with exactly $k$ parts equals the number of partitions of $n$ whose largest part is exactly $k$.


A partition of a positive integer $n$ is to write $n$ as a sum of some positive integers.. Show that the number of partitions of a positive integer $n$ into distinct parts is equal to the number of partitions of $n$ where all parts are odd integers.


Find the number of parallelograms in the following equilateral triangle of side length $n$ which is made of some smaller unit equilateral triangles.


Let $n$ be a positive integer. Find the number of paths from $(0,0)$ to $(n,n)$ on a $n\times n$ grid using only unit up and right steps so that the path stays in the region $x\ge y$.


Find the number of expressions containing $n$ pairs of parentheses which are correctly matched. For example, when $n=3$, the answer is $5$ because all the valid expressions are $$((())),\ (()()),\ (())(),\ ()(()),\ ()()()$$