�

Lunds Universitet

Datavetenskapliga institutionen

DAT 401 – DM

Prov på delkurs Diskret Matematik

18 april 2002 kl 8–13 MA9

Tillåtna hjälpmedel: Litteratur, egna anteckningar

Tentamen består av 3 uppgifter, varje uppgift kan ge 10 poäng. Deluppgifternas poäng anges inom [hakparenteser]. Observera att poänggivningen inte nödvändigtvis avspeglar deluppgiftens svårhetsgrad. Uppgifterna kan besvaras på svenska eller engelska.

Behandla högst en uppgift per papper (det går bra att behandla deluppgifter på samma papper). Skriv bara på ena sidan och markera varje sida med dina initialer. Skriv läsligt.

▶ a)[0] Hur många uppgifter får man behandla per papper? ▶ b)[0] Får man skriva på baksidan?

Det går bra att referera till kursboken av Rosen eller Husfeldts anteckningar. Referenser måste ha formen [R: något] eller [H: något], där något är ett avsnittsnummer, en kodbit, en räknad uppgift, etc. Skriv till exempel “genom att använda Lemma [R:7.4]”.

Exercise 1 (Sets, Probability)

A random subset R ⊆ {1, 2, …, n} is constructed by including every number i between 1 and n with probability p (0 ≤ p ≤ 1). For example, for p = \frac{1}{2} and n = 5 we can view this as flipping 5 coins, where ‘heads’ means ‘include the number in R’. The outcome

heads, heads, tails, heads, tails  (1)

would produce the set R = {1, 2, 4}.

Note. Except for the first two questions, you need to answer the following questions for general p (0 ≤ p ≤ 1) and general n (n ∈ Z, n ≥ 1).

▶ a)[1] Find p(R = \{1, 2, 4\}) for n = 5 and p = \frac{1}{2} . ▶ b)[1] Find p(R ⊆ \{1, 2, 4\}) for n = 5 and p = \frac{1}{2} . ▶ c)[1] Find p(R = ∅). ▶ d)[1] Find E(|R|).

Now pick another random subset S ⊆ {1, 2, …, n} (independently of R) in exactly the same way. For example, for p = \frac{1}{2} and n = 5 we now flip 10 coins (5 for R and 5 for S). The outcome

heads, heads, tails, heads, tails, tails, heads, heads, tails, tails  (2)

would produce the sets R = {1, 2, 4} and S = {2, 3}.

▶ e)[2] Find p(R ∩ S ≠ ∅). ▶ f)[2] Find E(|R ∩ S|). ▶ g)[2] Find p(R ∩ S ≠ ∅ | S ≠ ∅).

Exercise 2 (Combinatorics)

An n-gon is a convex polygon with n corners. Here are 5- 6- and 11-gons:

[figure]

An n-gon is triangulated by adding (non-crossing) lines between corners, let’s call these lines diagonals. The resulting figure shall consist only of triangles.

For example, there are two ways to triangulate the 4-gon: [figure] and [figure]. Especially note that these two triangulations are considered to be different (even though one is a rotation of the other). Here are some of the (different) triangulations of the 5-gon and the 6-gon:

[figure]

The Polygon Number P (n) is the number of ways to triangulate the (n + 2)- gon. For example, there were 2 ways to triangulate the 4-gon, so P (2) = 2. Let’s define P (0) = P (1) = 1 to make life easier for us.

▶ a)[1] Show that P (3) = 5. Find P (4). ▶ b)[1] How many diagonals are there in any triangulation of the k-gon? ▶ c)[2] How many ways are there to draw a single diagonal in an untriangulated

k-gon? For example, in the 5-gon, there are 5 such diagonals: [figure] [figure][figure] [figure] [figure]. ▶ d)[3] Give a combinatiorial argument for one of the following formulas (only one is

true, the other two are nonsense). Explicitly mention the Sum and Product rules if and when you use them in your argument.

•P (n) = ∑_{k=1}^{n} P (k − 1)P (n − k).
•P (n) = (n − 1)P (n − 1).
•P (n) = ∑_{k=0}^{n−1} P (k).

▶ e)[3] The Polygon numbers satisfy the recurrence relation

(n + 2)P (n + 1) = (4n + 2)P (n), n ≥ 0.

(You don’t need to give an argument for this.) Using this, show by induction:

P (n) = \frac{1}{n + 1} \binom{2n}{n}.

Exercise 3 (Recurrences)

Consider a variation of the Towers of Hanoi puzzle, which we will call Double Hanoi. There are 2n discs of n different sizes, two of each size. As usual we want to move one disc at a time, without moving a larger one on a smaller one.

Consider for example the first three moves for n = 2. (We use the notation (i → j) for moving the top disc of peg i to the top of peg j.)

(1 → 2)  (1 → 2)  (1 → 3)  ⋯

▶ a)[1] Finish the example for n = 2. Use the (i → j) notation instead of drawing lots of pretty pictures. State the total number of moves (including the first three moves from the example).

▶ b)[4] Find a recurrence relation for T_{n}, the number of moves needed to solve the Double Hanoi problem with 2n discs.

▶ c)[3] Solve the recurrence you found in the previous question. If you didn’t solve the previous question, solve D_{1} = 4, D_{n} = 3 + 3D_{n−1} instead.

▶ d)[2] Assume that there are kn discs, with k discs of every size. (The case k = 2 is the Double Hanoi problem, and the case k = 1 is standard Towers of Hanoi). Find a recurrence relation for the number of moves for this problem, and solve it.