Binom eng dvi

Problems for solving in train

1.1.

^{p−1 k}

<sub>2n

n</sub> p−1

_{n �} p−1

n
Prove that a) _k ≡ (−1) (mod p); b) _n ≡ (−4) ² (mod p) при ₂ .

2. 
   Prove that the number of odd binomial coefficients in n-th row of Pascal triangle is equal to 2^r, where
   

r is the number of 1’s in the binary expansion of n.

2. 
   Fix a positive integer m. By a m-arithmetical Pascal triangle we mean a triangle in which binomial coefficients are replaced by their residues modulo m. We will also consider similar triangles with the arbitrary residues a instead of 1’s along the lateral sides of the triangle. The operation of the multiplying by a number and addition of triangles of equal size are correctly defined. We will consider these operations modulo m.
   

+ =



n
Let all the elements of s-th row of m-arithmetical Pascal triangle except the first and the last one be equal to 0. Prove that the triangle has a form depicted on fig. 1. Shaded triangles consist of zeroes, triangles ∆^k

consist of s rows and satisfy the following relations


0

n

n

n+1

n

n
1) ∆^k−1 + ∆^k = ∆^k ; 2) ∆^k = C^k · ∆⁰ (mod m).

The well known puzzle Tower of Hanoi consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

1) оnly one disk may be moved at a time; 2) each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod; 3) no disk may be placed on top of a smaller disk.

^{Let n be the number of disks. Let TH}n ^{be a graph, whose vertices are all possible correct placements of disks onto 3 rods and edges connect placements that can be obtained one from another by 1 move. Consider also graph P}n^{, whose vertices are 1’s located in the first 2n rows of the 2-arithmetical Pascal triangle and edges connect neighboring 1’s (i.e. two adjacent 1’s in the same row or neighboring 1’s by a diagonal in two adjacent rows )}

2. 
   prove that graphs TH_n and P_n are isomorphic.
   
3. 
   Prove that that first 10⁶ rows of 2-arithmetical Pascal triangle contain less than 1 % of 1’s.
   

2. 
   Prove that if n is divisible by p − 1, then ⁿ + ⁿ
   

_{+ n}

+ . . . + ⁿ ≡ 1 (mod p). Or,

p−1 2(p−1) 3(p−1) n

even better prove the general statement: if 1 � j, k � p − 1 и n ≡ k (mod p − 1), then

n n n n k

+

j (p − 1) + j

+

2(p − 1) + j

+

3(p − 1) + j

+ . . . ≡ j

(mod p).

Рис. 1: Рис. 2: