�

Lunds Universitet

Datavetenskapliga institutionen

DAT 501 – DM

Prov på delkurs Diskret Matematik

29 november 2002 kl 14–19 MA10A-C

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 (Logic, Probability)

Given a sequence of Boolean variables x_{1}, …, x_{n} ∈ {T, F}, a random assignement gives the value

x_{i} = \{ \begin{matrix}T, & with probability p, \\ F, & with probability 1 − p. \end{matrix}

For p = \frac{1}{2} you can think of this as flipping a coin for each variable. If the coin comes up ‘heads’ then the variable is true, otherwise it’s false. For example, for p = \frac{1}{2} and n = 5 we can flip 5 coins like this:

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

which means that x_{1} = x_{2} = x_{4} = T and x_{3} = x_{5} = F. Under this random assignment the proposition x_{1} ∨ x_{5} happens to be true, but ¬x_{1} ∧ (x_{2} ∨ x_{5}) is false.

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(x_{1} ∧ x_{2} ∧ x_{4} = T) for n = 5 and p = \frac{1}{2} . ▶ b)[1] Find p(x_{1} ∨ x_{2} ∨ ¬x_{4} = T) for n = 5 and p = \frac{1}{2} . ▶ c)[1] Find p(x_{1} ∧ x_{2} ∧ ⋯ ∧ x_{n} = T), or, using other notation,

p(⋀_{i=1}^{n} x_{i} = T).

▶ d)[1] Find p(x_{1} ∨ x_{2} ∨ ⋯ ∨ x_{n}), or, using other notation,

p(⋁_{i=1}^{n} x_{i} = T).

▶ e)[1] Find p((x_{1} ∨ x_{2}) ∧ ¬(x_{3} ∨ x_{4}) = T). ▶ f)[1] (Harder) Find p((x_{1} ∨ x_{2}) ∧ (x_{1} ∨ x_{4}) = T). (Careful: the third variable is x_{1},

not x_{3}). ▶ g)[1] Find the probability that the conjunction of all variables is true given that

their disjunction is true, in symbols,

p(⋀_{i=1}^{n} x_{i} = T | ⋁_{i=1}^{n} x_{i} = T).

▶ h)[1] Find the probability that the disjunction of all variables is true given that their conjunction is true, in symbols,

p(⋁_{i=1}^{n} x_{i} = T | ⋀_{i=1}^{n} x_{i} = T).

Let the stochastic variable N denote the number of true variables, formally

N = |{ i | x_{i} = T }|.

For example, if x_{1} = x_{2} = x_{4} = T and x_{3} = x_{5} = F then N = 3.

▶ i)[2] Find E(N).

Exercise 2 (Combinatorics, induction)

Put two thick panes of glass (glasskivor) back-to-back. A ray of light (ljusstråle) can do two things at the boundaries: either it passes right through, or it is reflected. Below are three examples, showing rays that are reflected 0, 2, and 3 times, respectively. (The two glass panes are between the dotted lines, the ray of light is drawn as an arrow).

[figure: no reflections; two reflections; three reflections]

Note that there are many different way in which a ray can be reflected, since it can ‘bounce’ at any of the three boundaries. For example, if we want exactly two reflections, then there are three different ways to do it:

[figure]

Let B_{n} (the bounce number) denote the number of different ways a ray of light can be reflected exactly n times. We just saw that B_{2} = 3.

We also saw in the first picture that B_{0} = 1, since there is only one way to pass though the glass without getting reflected at all (namely, by passing right through it). And, to make life a little bit easier, let us agree that the ray actually needs to enter the glass panes, so the following does not count as a valid bounce:

[figure]

▶ a)[1] Show that B_{1} = 2 and B_{3} = 5. ▶ b)[1] Find B_{4}. ▶ c)[4] Give a combinatorial argument for the formula

B_{n} = B_{n−1} + B_{n−2}.

▶ d)[4] Prove by induction: For all n ≥ 0 we have

B_{0} + B_{1} + B_{2} + ⋯ + B_{n} = B_{n+2} − 2.

Exercise 3 (Recurrences)

Ancient Greeks defined the figurate numbers to be the number of dots in certain geometrical configurations. We will look at triangular numbers and pentagonal numbers in this exercise.

The first few triangular numbers are 1, 3, 6, and 10:

[figure: \begin{matrix}• \\ T_{1} = 1 \end{matrix}; •; •; •; T_{2} = 3; •; •; •; •; •; •; T_{3} = 6; •; •; •; •; •; •; •; •; •; •; T_{4} = 10]

▶ a)[1] Find the 5th triangular number T_{5}. ▶ b)[4] Find a recurrence relation for T_{n} (remember to include the base case). ▶ c)[2] Solve the recurrence you found in the previous question. If you didn’t solve

the previous question, solve D_{1} = 4, D_{n} = D_{n−1} + 2n instead.

The pentagonal numbers are defined similarly, but with pentagons instead of triangles. It’s also much harder to draw, so there are only three examples (P_{4} = 22, but I won’t draw it for you!).

[figure: \begin{matrix}• \\ P_{1} = 1 \end{matrix}; •; •; •; •; •; P_{2} = 5; •; •; •; •; •; •; •; •; •; •; •; •; •; P_{3} = 12]

▶ d)[3] Find and solve a recurrence relation for P_{n}.