Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.E: Fundamentals (Exercises)

( \newcommand{\kernel}{\mathrm{null}\,}\)

1.2: Examples

Exercise 1.E.2.1

Explain why an m×n board can be covered if either m or n is even. Explain why it cannot be covered if both m and n are odd.

Exercise 1.E.2.2

Suppose two diagonally opposite corners of an ordinary 8×8 board are removed. Can the resulting board be covered?

Exercise 1.E.2.3

Suppose that m and n are both odd. On an m×n board, colored as usual, all four corners will be the same color, say white. Suppose one white square is removed from the board. Show that the resulting board can be covered.

Exercise 1.E.2.4

Suppose that one corner of an 8×8 board is removed. Can the remainder be covered by 1×3 tiles? Show a tiling or prove that it cannot be done.

Exercise 1.E.2.5

Suppose the square in row 3, column 3 of an 8×8 board is removed. Can the remainder be covered by 1×3 tiles? Show a tiling or prove that it cannot be done.

Exercise 1.E.2.6

Remove two diagonally opposite corners of an m×n board, where m is odd and n is even. Show that the remainder can be covered with dominoes.

Exercise 1.E.2.7

Suppose one white and one black square are removed from an n×n board, n even. Show that the remainder can be covered by dominoes.

Exercise 1.E.2.8

Suppose an n×n board, n even, is covered with dominoes. Show that the number of horizontal dominoes with a white square under the left end is equal to the number of horizontal dominoes with a black square under the left end.

Exercise 1.E.2.9

In the complete graph on five vertices shown above, there are five pairs of edges that cross. Draw this graph so that only one pair of edges cross. Remember that "edges'' do not have to be straight lines.

Exercise 1.E.2.10

The complete bipartite graph K3,3 consists of two groups of three vertices each, with all possible edges between the groups and no other edges:

clipboard_e39f4758ac054e15cc02283a7cae56d71.png
Figure 1.E.1

Draw this graph with only one crossing.

1.3: Combinations and Permutations

Exercise 1.E.3.1

How many positive factors does 23473112475 have? How many does pe11pe22penn have, where the pi are distinct primes?

Exercise 1.E.3.2

A poker hand consists of five cards from a standard 52 card deck with four suits and thirteen values in each suit; the order of the cards in a hand is irrelevant. How many hands consist of 2 cards with one value and 3 cards of another value (a full house)? How many consist of 5 cards from the same suit (a flush)?

Exercise 1.E.3.3

Six men and six women are to be seated around a table, with men and women alternating. The chairs don't matter, only who is next to whom, but right and left are different. How many seating arrangements are possible?

Exercise 1.E.3.4

Eight people are to be seated around a table; the chairs don't matter, only who is next to whom, but right and left are different. Two people, X and Y, cannot be seated next to each other. How many seating arrangements are possible?

Exercise 1.E.3.5

In chess, a rook attacks any piece in the same row or column as the rook, provided no other piece is between them. In how many ways can eight rooks be placed on a chess board so that no two attack each other? What about eight rooks on a 10×10 board?

Exercise 1.E.3.6

Suppose that we want to place 8 non-attacking rooks on a chessboard. In how many ways can we do this if the 16 most `northwest' squares must be empty? How about if only the 4 most `northwest' squares must be empty?

Exercise 1.E.3.7

A "legal'' sequence of parentheses is one in which the parentheses can be properly matched, like ()(()). It's not hard to see that this is possible precisely when the number of left and right parentheses is the same, and every initial segment of the sequence has at least as many left parentheses as right. For example, ()) cannot possibly be extended to a legal sequence. Show that the number of legal sequences of length 2n is Cn=(2nn)(2nn+1). The numbers Cn are called the Catalan numbers.

1.4: Binomial Coefficients

Exercise 1.E.4.1

Suppose a street grid starts at position (0,0) and extends up and to the right:

clipboard_eae8c8555aefde996137e5d581fb01ca5.png
Figure 1.E.1

A shortest route along streets from (0,0) to (i,j) is i+j blocks long, going i blocks east and j blocks north. How many such routes are there? Suppose that the block between (k,l) and (k+1,l) is closed, where k<i and lj. How many shortest routes are there from (0,0) to (i,j)?

Exercise 1.E.4.2

Prove by induction that nk=0(ki)=(n+1i+1) for n0 and i0.

Exercise 1.E.4.3

Use a combinatorial argument to prove that nk=0(ki)=(n+1i+1) for n0 and i0; that is, explain why the left-hand side counts the same thing as the right-hand side.

Exercise 1.E.4.4

Use a combinatorial argument to prove that (k2)+(nk2)+k(nk)=(n2).

Exercise 1.E.4.5

Use a combinatorial argument to prove that (2nn) is even.

Exercise 1.E.4.6

Suppose that A is a non-empty finite set. Prove that A has as many even-sized subsets as it does odd-sized subsets.

Exercise 1.E.4.7

Prove that nk=0(ki)k=(n+1i+1)n(n+1i+2) for n0 and i0.

Exercise 1.E.4.8

Verify that (n+12)+(n2)=n2. Use Exercise 1.E.4.2 to find a simple expression for ni=1i2.

Exercise 1.E.4.9

Make a conjecture about the sums of the upward diagonals in Pascal's Triangle as indicated. Prove your conjecture is true.

clipboard_edf9745e6394ec522ee9a5385c4cc6217.png
Figure 1.E.2
Exercise 1.E.4.10

Find the number of ways to write n as an ordered sum of ones and twos, n0. For example, when n=4, there are five ways: 1+1+1+1, 2+1+1, 1+2+1, 1+1+2, and 2+2.

Exercise 1.E.4.11

Use (x+1)n=ni=0(ni)xi to find a simple expression for ni=01i+1(ni)xi+1. Then find a simple expression for ni=01i+1(ni).

Exercise 1.E.4.12

Use the previous exercise to find a simple expression for ni=0(1)i1i+1(ni).

Exercise 1.E.4.13

Give a combinatorial proof of ki=0(mi)(nki)=(m+nk). Rewrite this identity in simpler form if m=n, and when k=m=n.

Exercise 1.E.4.14

Finish the proof of Theorem 1.4.3.

Exercise 1.E.4.15

Give an alternate proof of Theorem 1.4.3 by characterizing those i for which (ni)/(ni1)>1.

Exercise 1.E.4.16

When is (ni)/(ni1) a maximum? When is (ni)/(ni1)=2?

Exercise 1.E.4.17

When is (ni)(ni1) a maximum?

Exercise 1.E.4.18

A Galton board is an upright flat surface with protruding horizontal pins arranged as shown below. At the bottom are a number of bins; if the number of rows is n, the number of bins is n+1. A ball is dropped directly above the top pin, and at each pin bounces left or right with equal probability. We assume that the ball next hits the pin below and immediately left or right of the pin it has struck, and this continues down the board, until the ball falls into a bin at the bottom. If we number the bins from 0 to n, how many paths can a ball travel to end up in bin k?

This may be interpreted in terms of probability, which was the intent of Sir Francis Galton when he designed it. Each path is equally likely to be taken by a ball. If many balls are dropped, the number of balls in bin k corresponds to the probability of ending up in that bin. The more paths that end in a bin, the higher the probability. When a very large number of balls are dropped, the balls will form an approximation to the bell curve familiar from probability and statistics.

There is an animation of the process at http://www.math.uah.edu/stat/apps/GaltonBoardExperiment.html. There was once a very nice physical implementation at the Pacific Science Center in Seattle.

clipboard_e4ca91ce3a03e8d07322ad7ecb2f95920.png
Figure 1.E.3

1.5: Bell Numbers

Exercise 1.E.5.1

Show that if {A1,A2,,Ak} is a partition of {1,2,,n}, then there is a unique equivalence relation whose equivalence classes are {A1,A2,,Ak}.

Exercise 1.E.5.2

Suppose n is a square-free number, that is, no number m2 divides n; put another way, square-free numbers are products of distinct prime factors, that is, n=p1p2pk, where each pi is prime and no two prime factors are equal. Find the number of factorizations of n. For example, 30=235, and the factorizations of 30 are 30, 65, 103, 215, and 235. Note we count 30 alone as a factorization, though in some sense a trivial factorization.

Exercise 1.E.5.3

The rhyme scheme of a stanza of poetry indicates which lines rhyme. This is usually expressed in the form ABAB, meaning the first and third lines of a four line stanza rhyme, as do the second and fourth, or ABCB, meaning only lines two and four rhyme, and so on. A limerick is a five line poem with rhyming scheme AABBA. How many different rhyme schemes are possible for an n line stanza? To avoid duplicate patterns, we only allow a new letter into the pattern when all previous letters have been used to the left of the new one. For example, ACBA is not allowed, since when C is placed in position 2, B has not been used to the left. This is the same rhyme scheme as ABCA, which is allowed.

Exercise 1.E.5.4

Another way to express the Bell numbers for n>0 is Bn=nk=1S(n,k), where S(n,k) is the number of partitions of {1,2,,n} into exactly k parts, 1kn. The S(n,k) are the Stirling numbers of the second kind . Find a recurrence relation for S(n,k). Your recurrence should allow a fairly simple triangle construction containing the values S(n,k), and then the Bell numbers may be computed by summing the rows of this triangle. Show the first five rows of the triangle, n{1,2,,5}.

Exercise 1.E.5.5

Let An be the number of partitions of {1,2,,n+1} in which no consecutive integers are in the same part of the partition. For example, when n=3 these partitions are {{1},{2},{3},{4}}, {{1},{2,4},{3}}, {{1,3},{2},{4}}, {{1,3},{2,4}}, {{1,4},{2},{3}}, so A3=5. Let A(n,k) be the number of partitions of {1,2,,n+1} into exactly k parts, in which no consecutive integers are in the same part of the partition. Thus An=n+1k=2A(n,k). Find a recurrence for A(n,k) and then show that An=Bn.

1.6: Choice with Repetition

Exercise 1.E.6.1

Suppose a box contains 18 balls numbered 1–6, three balls with each number. When 4 balls are drawn without replacement, how many outcomes are possible? Do this in two ways: assuming that the order in which the balls are drawn matters, and then assuming that order does not matter.

Exercise 1.E.6.2

How many permutations are there of the letters in Mississippi?

Exercise 1.E.6.3

How many permutations are there of the multiset {1a1,1a2,,1an}?

Exercise 1.E.6.4

Let M=ni=1mi. If ki<0, let's say (Mk1k2kn)=0.

Prove that (Mm1m2mn)=ni=1(M1m1m2(mi1)mn).

Note that when n=2 this becomes (Mm1m2)=(M1(m11)m2)+(M1m1(m21)).

As noted above in Equation (1.6.1), when n=2 we are really seeing ordinary binomial coefficients, and this can be rewritten as (Mm1)=(M1m11)+(M1m1), which of course we already know.

Exercise 1.E.6.5

The Binomial Theorem 1.4.1 can be written (x+y)n=i+j=n(nij)xiyj, where the sum is over all non-negative integers i and j that sum to n. Prove that for m2, (x1+x2++xm)n=(ni1i2im)xi11xi22ximm. where the sum is over all i1,,im such that i1++im=n.

1.7: The Pigeonhole Principle

Exercise 1.E.7.1

Assume that the relation "friend'' is symmetric. Show that if n2, then in any group of n people there are two with the same number of friends in the group.

Exercise 1.E.7.2

Suppose that 501 distinct integers are selected from 11000. Show that there are distinct selected integers a and b such that a|b. Show that this is not always true if 500 integers are selected.

Exercise 1.E.7.3

Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the balls. Show there are at least two pairs, consisting of one red and one green ball, with the same value. Show that this is not true if there are 13 balls of each color.

Exercise 1.E.7.4

Suppose (a1,a2,,a52) are integers, not necessarily distinct. Show that there are two, ai and aj with ij, such that either ai+aj or aiaj is divisible by 100. Show that this is not necessarily true for integers (a1,a2,,a51).

Exercise 1.E.7.5

Suppose five points are chosen from a square whose sides are length s. (The points may be either in the interior of the square or on the boundary.) Show that two of the points are at most s2/2 apart. Find five points so that no two are less than s2/2 apart.

Exercise 1.E.7.6

Show that if the edges of K6 are colored with two colors, there are at least two monochromatic triangles. (Two triangles are different if each contains at least one vertex not in the other. For example, two red triangles that share an edge count as two triangles.) Color the edges of K6 so that there are exactly two monochromatic triangles.

Exercise 1.E.7.7

Suppose the edges of a K5 are colored with two colors, say red and blue, so that there are no monochromatic triangles. Show that the red edges form a cycle, and the blue edges form a cycle, each with five edges. (A cycle is a sequence of edges {v1,v2},{v2,v3},,{vk,v1}, where all of the vi are distinct. Note that this is true in Figure 1.7.1).

Exercise 1.E.7.8

Show that 8<R(3,4)10.

Exercise 1.E.7.9

Show that R(3,4)=9.

1.8: Sperner's Theorem

Exercise 1.E.8.1

Sperner's Theorem (1.8.1) tells us that [63], with size 20, is the unique largest anti-chain for 2[6]. The next largest anti-chains of the form [6k] are [62] and [64], with size 15. Find a maximal anti-chain with size larger than 15 but less than 20. (As usual, maximal here means that the anti-chain cannot be enlarged simply by adding elements. So you may not simply use a subset of [63].)

1.9: Stirling Numbers

Exercise 1.E.9.1

Find a simple expression for [nn1].

Exercise 1.E.9.2

Find a simple expression for [n1].

Exercise 1.E.9.3

What is nk=0[nk]?

Exercise 1.E.9.4

What is nk=0s(n,k)?

Exercise 1.E.9.5

Show that xn_=n1k=0(xk)=ni=0s(n,i)xi, n1; xn_ is called a falling factorial. Find a similar identity for x¯n=n1k=0(x+k); x¯n is a rising factorial.

Exercise 1.E.9.6

Show that nk=0{nk}xk_=xn, n1; xk_ is defined in the previous exercise. The previous exercise shows how to express the falling factorial in terms of powers of x; this exercise shows how to express the powers of x in terms of falling factorials.

Exercise 1.E.9.7

Prove: S(n,k)=n1i=k1(n1i)S(i,k1).

Exercise 1.E.9.8

Prove: [nk]=n1i=k1(ni1)!(n1i)[ik1].

Exercise 1.E.9

Use the previous exercise to prove s(n,k)=n1i=k1(1)ni1(ni1)!(n1i)s(i,k1).

Exercise 1.E.10

We have defined [nk] and {nk} for n,k0. We want to extend the definitions to all integers. Without some extra stipulations, there are many ways to do this. Let us suppose that for n0 we want [n0]=[0n]={n0}={0n}=0, and we want the recurrence relations of equation 1.9.1 and in Theorem 1.9.1 to be true. Show that under these conditions there is a unique way to extend the definitions to all integers, and that when this is done, {nk}=[kn] for all integers n and k. Thus, the extended table of values for either [nk] or {nk} will contain all the values of both [nk] and {nk}.

Exercise 1.E.11

Under the assumptions that s(n,0)=s(0,n)=0 for n0, and s(n,k)=s(n1,k1)(n1)s(n1,k), extend the table for s(n,k) to all integers, and find a connection to S(n,k) similar to that in the previous problem.

Exercise 1.E.12

Prove Corollary 1.9.1.

Exercise 1.E.13

Prove the remaining part of Theorem 1.9.2.


This page titled 1.E: Fundamentals (Exercises) is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?