Prove that for n⩾1n \geqslant 1n⩾1 and m⩾0m \geqslant 0m⩾0 the following equality holds: Fn+m=Fn−1Fm+FnFm+1F_{n+m} = F_{n-1} F_{m} + F_{n} F_{m+1}Fn+m=Fn−1Fm+FnFm+1 Try to prove it in two ways: using the method of mathematical induction and using the Fibonacci number…
Let SSS be a set of intervals defined recursively as follows: - Initially, [1,1000][1,1000][1,1000] is the only interval in SSS . - If l≠rl\neq rl=r and [l,r]∈S[l,r]\in S[l,r]∈S , then both…
There are n(>1)n (>1)n(>1) points on a circle, labeled as p1,p2,⋯ ,pnp_{1}, p_{2}, \cdots, p_{n}p1,p2,⋯,pn. Determine the number of ways to connect these points with a non-self-intersecting polyline p1p2⋯pnp_{1} p_{2} \cdots p_{n}p1p2⋯pn.
Let nnn be an integer greater than 3. Let RRR be the set of lattice points (x,y)(x, y)(x,y) such that 0≤x,y≤n0 \leq x, y \leq n0≤x,y≤n and ∣x−y∣≤3|x-y| \leq 3∣x−y∣≤3. Let AnA_nAn be the number of paths from (0,0)(0,0)(0,0) to (n,n)(n,n)(n,n) that consist onl…
Suppose you have an equilateral triangle divided into 9 smaller equilateral triangles with the bottom side horizontal. Starting from the top corner labeled AAA, you must walk to the bottom right corner labeled BBB, and are only allo…
Prove that the number of partitions of a set, denoted by S(n,k)S(n, k)S(n,k), satisfies the recurrence relation S(n+1,k)=S(n,k−1)+k⋅S(n,k)S(n+1, k) = S(n, k-1) + k \cdot S(n, k)S(n+1,k)=S(n,k−1)+k⋅S(n,k) for 1≤k≤n1 \leq k \leq n1≤k≤n. Use this relation to calculate S(5,3)S(5, 3)S(5,3).
Lennart and Eddy are playing a betting game. Lennart starts with 777 dollars and Eddy starts with 333 dollars. Each round, both Lennart and Eddy bet an amount equal to the amount of the player with the least money. For example, on the f…
We call a set of positive integers "tyû-de-jó" if there are no two numbers in the set whose difference is 2. How many "tyû-de-jó" subsets are there of the set {1,2,3,…,10}\{1,2,3, \ldots, 10\}{1,2,3,…,10}?
Each cell of a 2×52 \times 52×5 grid of unit squares is to be colored white or black. Compute the number of such colorings for which no 2×22 \times 22×2 square is a single color.
Prove the equality: Cn0+Cn−11+Cn−22+…=Fn+1C_{n}^{0}+C_{n-1}^{1}+C_{n-2}^{2}+\ldots=F_{n+1}Cn0+Cn−11+Cn−22+…=Fn+1. (The sum on the left-hand side can be interpreted as the sum of the elements of Pascal's triangle that lie on one diagonal.)
There is a standard deck of 525252 cards without jokers. The deck consists of four suits(diamond, club, heart, spade) which include thirteen cards in each. For each suit, all thirteen cards are ranked from “ 222 ” to “ AAA ” (i.e.…
In a 2×82 \times 82×8 squared board, you want to color each square red or blue in such a way that on each 2×22 \times 22×2 sub-board there are at least 333 boxes painted blue. In how many ways can this coloring be done? Note. A 2×22 \times 22×2…
Let nnn be a positive integer. Let a(n)a(n)a(n) denote the number of partitions of nnn of the form n=x1+x2+…n = x_1 + x_2 + \ldotsn=x1+x2+… where x1≤x2≤…x_1 \leq x_2 \leq \ldotsx1≤x2≤… and for every term xix_ixi in the sequence, xi+1x_i + 1xi+1 is a pow…
A dog has three trainers: - The first trainer gives him a treat right away. - The second trainer makes him jump five times, then gives him a treat. - The third trainer makes him jump three times, then gives him no treat. The dog will ke…
Find the number of positive integers j≤32013j \leq 3^{2013}j≤32013 such that j=∑k=0m((−1)k⋅3ak)j = \sum_{k=0}^{m} \left((-1)^k \cdot 3^{a_k}\right)j=∑k=0m((−1)k⋅3ak for some strictly increasing sequence of nonnegative integers {ak}\{a_k\}{ak}. For example, we may write…
Misha rolls a standard, fair six-sided die until she rolls 1−2−31-2-31−2−3 in that order on three consecutive rolls. The probability that she will roll the die an odd number of times is mn\dfrac{m}{n}nm where mmm and nnn are relatively prime positive…
Let ∠A\angle A∠A and ∠E\angle E∠E be two opposite vertices of a regular octagon. A frog starts jumping from vertex AAA. At each vertex other than EEE, the frog can jump to either of the two adjacent vertices. The frog stops once it reaches vert…
We color all vertexs of a convex polygon with 101010 vertexs by 222 colors: red and blue ((( each vertex is colored by 111 color ).).). How many ways to color all the vertexs such that there are no 222 adjacent vertex that are both col…
The function f:Z2→Zf: \mathbb{Z}^{2} \rightarrow \mathbb{Z}f:Z2→Z satisfies the following conditions: - f(x,0)=f(0,y)=0f(x, 0) = f(0, y) = 0f(x,0)=f(0,y)=0 - f(x,y)=f(x−1,y)+f(x,y−1)+x+yf(x, y) = f(x-1, y) + f(x, y-1) + x + yf(x,y)=f(x−1,y)+f(x,y− for all nonnegative integers xxx and yyy. Find…
If a coin lands on the same side kkk times in a row, we will call such a subsequence a group of length kkk. For example, in the sequence HHTHHTHH there are four groups, with lengths 1,2,21, 2, 21,2,2 and 222, respectively. Denote pn,kp_{n, k}pn,k as the…