Hints to exercises
1008
94
99
10
18
16
300
1800
Just apply the definition.
\(6+6^2+6^3+6^4+6^5+6^6=55986\)
15
\(\binom{9}{4}\)
There are \(2^n\) subsets for an \(n\)-element set.
\(\binom{n}{2}\)
\(m^n\) functions
\(2^{mn}\) relations
The graph in top left and the one in the bottom right have an Eulerian circuit. The graph in the top right has an Eulerian path. The graph in the bottom left has neither an Eulerian path nor an Eulerian circuit.
Let \(G\) be a graph with \(m\) edges and \(n\) nodes \(v_1,\ldots,v_n.\) Suppose that \(v_1,\ldots,v_r\) are all the odd nodes. Theorem 7.2 gives \[\sum_{i = 1}^r \deg(v_i) + \sum_{i=r+1}^n \deg(v_i) = 2m.\] Since \(\deg(v_i)\) is even for \(i = r+1,\ldots,n,\) we see that \(\sum\limits_{i = 1}^r \deg(v_i)\) is even, implying that \(r\) is even since \(\deg(v_i)\) is odd for \(i = 1,\ldots,r.\)
Each domino will cover one white square and one black square. However, pruning from diagonally opposite corners removes two squares of the same colour, yielding 30 squares of one colour and 32 squares of the other colour. Thus, no tiling with dominoes can cover all the squares.
Let the board size be \((2k+1)\times (2k+1)\) for some nonnegative integer \(k.\) After removing a square the same colour as one of its corners, there remain \((2k+1)^2-1\) square to tile and there are \(2k^2+2k\) squares of each colour. We number the rows from \(1\) to \(2k+1\) starting from the top. We consider two cases.
Case 1. The pruned square is in an odd-numbered row. Observe that the row with the pruned square must have an even number of squares to the left of the pruned square and an even number of squares tot he right of the pruned square. Thus, this row can be tiled horizontally with dominoes. Now, there are an even number of rows above the pruned square as well as an even number of rows below the pruned square. We can tile these rows two rows at a time with \(2k+1\) dominoes laid down vertically from left to right.
Case 2. The pruned square is in row \(r\) where \(r\) is even. Start tiling row \(r-1\) horizontally from left to right. Cover the last square of row \(r-1\) and the square right below by laying down a domino vertically. Now, row \(r\) will have an even number of untiled squares on the right of the pruned square and an odd number of untiled squares on the left of the pruned square. Tile row \(r\) horizontally from right to left, skipping over the pruned square. Tile the leftmost square of row \(r\) and the square below it by laying down a domino vertically. This leaves an even number of squares in row \(r+1\) to tile horizontally. The number of rows above row \(r-1\) and that below row \(r+1\) are even and can be tiled easily.
In a \(4\times 5\) chessboard, there are 10 white squares and 10 black squares. Of the five tetrominoes, four will cover exactly two squares of each colour. However, the T piece must cover three of the same colour and one of the other colour. Thus, a tiling of the chessboard using the five tetrominoes will cover nine squares of one colour and elevent of the colour, contradicting that there are 10 white squares and 10 black squares on the chessboard.
A connected graph has an Eulerian circuit if and only if every node has even degree.
A connected graph has an Eulerian path if and only if there are exactly two nodes of odd degree.
A magic square of order 4: \(\begin{array}{|c|c|c|c|} \hline 16 & 3 & 2 & 13 \\ \hline 5 & 10 & 11 & 8 \\ \hline 9 & 6 & 7 & 12 \\ \hline 4 & 15 & 14 & 1 \\ \hline \end{array}\)
A magic square of order 5: \(\begin{array}{|c|c|c|c|c|} \hline 1 & 15 & 24 & 8 & 17 \\ \hline 23 & 7 & 16 & 5 & 14 \\ \hline 20 & 4 & 13 & 22 & 6 \\ \hline 12 & 21 & 10 & 19 & 3 \\ \hline 19 & 18 & 2 & 11 & 2 \\ \hline \end{array}\)
No.
Yes.
The average person has roughly 100,000 hairs. It is safe to assume that no person has ten times this number of hairs. Hence, an upper bound for the number of hairs on a head would be one million. As the population of New York is roughly 8.53 million as of 2017, by the pigeonhole principle, there must be more than one person with the same number of hairs on their heads.
Four.
Let \(A\) denote the set \(\{1,2,3,\ldots,2000\}.\) Let \(O\) denote the set of odd numbers in \(A.\) Define a function \(f:A \rightarrow O\) as follows: for an \(x \in A,\) \(f(x) = m\) where \(m\) is an odd natural number such that \(x = 2^k m\) for some nonnegative integer \(k.\) (Note that \(k\) and \(m\) are unique by the Fundamental Theorem of Arithmetic.) Now, for any subset \(C \subseteq A,\) \(|f(C)| \leq |O| = 1000.\) Thus, if \(|C| = 1001,\) there must exist distinct \(u, v \in C\) such that \(f(u) = f(v),\) implying that \(u = 2^k m\) and \(v = 2^{k'} m\) for some odd natural number \(m\) and nonnegative integers \(k\) and \(k'.\) If \(k \leq k',\) then \(u\) divides \(v.\) Otherwise, \(v\) divides \(u.\)
Define \(S_0,S_1,\ldots,S_{51}\) as follows: \(S_0 = \{0\}\) and \(S_i = \{i, 103-i\}\) for \(i = 1,\ldots, 51.\) Note that if \(x\) is an integer, then its remainder when divided by \(103\) must be in \(S_j\) for some \(j \in \{0,\ldots, 51\}.\) If there are \(53\) integers, then by the pigeonhole principles, two of them will have remainders in the same \(S_k\) for some \(k.\) It is easy to see that either the sum or the difference of these two numbrs will be evenly divisible by \(103.\)
Divide the square into nine smaller squares, each with side length 1. Since there are 10 points placed in the square, by the pigeonhole principle, there must be two points that are in the same smaller square. The result now follows because the maximum distance between two points in a square of side length 1 is \(\sqrt{2}.\)
Try something similar to the previous question.
It is actually easier to prove this by induction on the number of edges in the graph. To prove this using the pigeonhole principle, note that it suffices to prove the result for connected graphs. (A graph is connected if there is a path from one node to any other node.) A simple induction shows that, in a connected graph, the number of nodes must be at least one more than the number of edges. If there are \(m\) edges, then \(1,2,\ldots,m\) are the only possible values for the degree (0 is not possible since the graph is connected and has at least two nodes) but at least \(m+1\) degree values coming from the nodes.
Using the Binomial Theorem, we have \[\begin{align*} 1001^6 & = (1000+1)^6 \\ & = \sum_{i = 0}^6 \binom{6}{i} 1000^{6-i} \cdot 1^i \\ & = 1000^6 + 6\cdot 1000^5 + 15 \cdot 1000^4 + 20 \cdot 1000^3 + 15\cdot 1000^2 + 6\cdot 1000 + 1 \\ & = 1006015020015006001. \end{align*}\]
\(2x^5 + 30x^4 + 180x^3 + 540x^2 + 810x + 243\)
\(x^{12} + 6 x^{10} y^2 + 15 x^8 y^4 + 20 x^6 y^6 + 15 x^4 y^8 + 6 x^2 y^{10}+y^{12}\)
The next layer looks like \[\begin{array}{cccccccccc} & & & & 1 & & & & & \\ & & & 4 & & 4 & & & & \\ & & 6 & & 10 & & 6 & & & \\ & 4 & & 10 & & 10 & & 4 & & \\ 1 & & 4 & & 6 & & 4 & & 1 & \end{array}\]
There are \(\binom{210}{24}\) possible student governments. For each student government, there are \(\binom{24}{5}\) possible steering committees. Thus, the total number of possible governance structures is \(\binom{210}{24}\binom{24}{5}.\) Another way to obtain the formula is that there are a total of \(\binom{210}{5}\) steering commmittees that can be formed from all the student membres. Once the steering committee is chosen, there are \(\binom{210-5}{24-5}\) ways to complete a student government starting with the steering committee. Hence, there are a total of \(\binom{210}{5}\binom{205}{19}\) possible governance structures.
Use a similar argument as in the previous question.
Use induction on \(n.\) At some point, you will probably need the following identity: \[\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}\] for \(1 \leq k \leq n.\)