Chapter 7

Use the binomial theorem (with \(x=1000\) and \(y=1\) ) to calculate \(1001^{6} .\)

Find \((2 x+3)^{5}\).

If we select 1001 numbers from the set \(\\{1,2,3, \ldots, 2000\\}\) it is certain that there will be two numbers selected such that one divides the other. We can prove this fact by noting that every number in the given set can be expressed in the form \(2^{k} \cdot m\) where \(m\) is an odd number and using the pigeonhole principle. Write-up this proof.

Provide an argument as to why an \(8 \times 8\) chessboard with two squares pruned from diagonally opposite corners cannot be tiled with dominoes.

Given any set of 53 integers, show that there are two of them having the property that either their sum or their difference is evenly divisible by 103.

The student government at Lagrange High consists of 24 members chosen from amongst the general student body of \(210 .\) Additionally, there is a steering committee of 5 members chosen from amongst those in student government. Use the multiplication rule to determine two different formulas for the total number of possible governance structures.

Prove that if 10 points are placed inside a square of side length 3 , there will be 2 points within \(\sqrt{2}\) of one another.

Prove the identity $$ \left(\begin{array}{l} n \\ k \end{array}\right) \cdot\left(\begin{array}{l} k \\ r \end{array}\right)=\left(\begin{array}{l} n \\ r \end{array}\right) \cdot\left(\begin{array}{l} n-r \\ k-r \end{array}\right) $$ combinatorially.

Prove that if 10 points are placed inside an equilateral triangle of side length \(3,\) there will be 2 points within 1 of one another.

State necessary and sufficient conditions for the existence of an Eulerian circuit in a graph.

Prove the binomial theorem. $$ \forall n \in \mathbb{N}, \forall x, y \in \mathbb{R},(x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k} $$

Prove that in a simple graph (an undirected graph with no loops or parallel edges) having \(n\) nodes, there must be two nodes having the same degree.

State necessary and sufficient conditions for the existence of an Eulerian path in a graph.