Mathematical Foundations

of
Computer Science
CS 499, Shanghai Jiaotong University, Dominik Scheder

• Homework assignment published on Monday, 2017-02-20

• Work on it and submit questions by Wednesday, 2017-02-22, 18:00 by

email to [email protected]

• We will discuss some problems on Thursday, 2017-02-23.

• Submit your solution by Sunday, 2017-02-26 to me and TA.

• We will give you feedback, you will have an opportunity to revise your
solution before we will grade it.

• Sample solution posted on Friday, 2017-03-10

This is the sample solution of Homework 1. Here, I posted solutions

also to very simple problems to give you an idea (1) how you should write
your solutions, (2) how formal you should be. In the future, I will only post
solutions to selected homework problems.

1 Broken Chessboard and Jumping With Coins

1.1 Tiling a Damaged Checkerboard
In the video lecture you have seen a proof that one cannot tile the “damaged”
8 × 8 checkerboard with domino stones:

1
Exercise 1.1. Re-write the proof in your own way, using simple English
sentences.

Exercise 1.2. Look at the seriously damaged 8 × 8 checkerboard. For con-

venience I already colored it black and white (or rather black and beige):

Try to tile it with domino stones and you will fail. However, since there are
24 black and 24 beige squares, the simple argument from the lecture will fail.
Prove that the above board cannot be tiled. Try to find a short and
simple argument!

Proof. Consider the three leftmost columns (the area within the blue bound-
ary). Two black squares have been sawed off, so there are 12 orange and 10
black ones left in this 8×3 rectangle. In a complete tiling, each of these 12 or-
ange squares would have to be paired with a black one. Which black squares
are eligible for this? Well, clearly the 10 black squares within the three left-
most columns, plus the one marked red. Thus, the 12 orange squares in the

2
three leftmost columns have 11 eligible “partners”. Not enough to match
everyone.

1.2 Jumping with Coins

This is simply a reminder of the exercises I posed in the video lecture. For
details, refer to the video.
Remark. The following exercises are of different levels of difficulty, but
they all have a very simple proof (altough the proof might not be easy to
find).
Exercise 1.3. You jump around with two coins. Show that you cannot
increase the distance between the two coins.

Every jump leaves the distance unchanged, thus it is not possible.

Exercise 1.4. You jump around with three coins. Show that you cannot
start with an equilateral triangle and end up with a bigger equilateral trian-
gle. Give a simple proof!

Every jump leaves the area of the triangle unchanged, thus it is not pos-
sible.

To be more formal, suppose the three coins are at points A, B, C. Without

loss of generality we jump with the coin at A over the one at B, landing at
a new position A0 .

3
 C

A B A0
Note that both triangles have height h, and the length of the side opposite
C remains unchanged: ||A − B|| = ||A0 − B||. Thus, both areas are the same.

You jump around with four coins which in the beginning form a square
of side length 1.

Exercise 1.5. Show that you cannot form a square of side length 2.
We can imagine the coins to lie on a checkerboard that is colored black
and white.

Note that the “color of a coin” will never change. In the length-1 square,
two coins are white and two are black. In a length-2 square, either all are
white or all are black. Thus, it is impossible to transform the former into the
latter.

4
Exercise 1.6. Show that you cannot achieve a position in which two coins
are at the same position.

First of all, the above proof will not work anymore. There are two white
coins in the beginning, so it is not clear why we cannot make these two coins
lie on top of each other. We need a more fine-grained coloring:

That is, we use four colors instead. Again, a coin will never change its color.
In the beginning, i.e., in the square of side length 1, all colors are different.
Thus, two coins can never land on the same position.

Exercise 1.7. Show that you cannot form a larger square.

First we will show that we cannot form a smaller square: indeed, imagine
the square being of sidelength 1 and placed on an integer grid. The coins
always stay on the integer grid, thus a sidelength of less than 1 is impossible
to achieve.
Now suppose that we can transform a square into larger one. Since every
move is reversible, we can also transform a square into a smaller one. But
this is impossible, as shown above.
Thus, we cannot make a square larger.

Also note that all above proofs break down. A square of sidelength 3
would again have all four colors distinct, so the previous proof does not
work. Also arguing with area does not work. It is not clear which triangle
to measure, since there are four coins. In fact, it is possible to make the area
enclosed by the four coins larger.

*Exercise 1.8. We can denote a “coin configuration” as a tuple (a, b, c, d)

where a, b, c, d ∈ R2 . Let U = (a, b, c, d) and V = (a0 , b0 , c0 , d0 ) be two coin

5
configurations. We write U → V if we can go from U to V by jumping and
U 6→ V if not. For example,

((0, 0), (1, 0), (0, 1), (1, 1)) → ((0, 1), (0, 2), (1, 0), (1, 1)) but
((0, 0), (1, 0), (0, 1), (1, 1)) 6→ ((0, 0), (2, 0), (0, 2), (2, 2)) and certainly
√ √ √
((0, 0), (1, 0), (0, 1), (1, 1)) 6→ ((0, 0.5), (π, 0), (0, 2), ( 3, 5)) .

Can you find a general principle by which we can determine whether U → V ?

Formally, can you find a simple and efficient algorithm which, on input U, V ,
determines whether U → V holds?

Actually, I don’t know. I’d proceed as follows. For points u1 , . . . , uk ∈ R2 ,

we define the affine lattice Λ(u1 , . . . , uk ) to be the set
( k
)
X
λ1 u1 + · · · + λk uk |λi ∈ Z and λi = 1 .
i=1

For example, the vector 2u1 − u2 is in the lattice, since 2 and −1 are integers
and sum up to 1. Note that 2u1 − u2 is also where you end up if you jump
with a coin at u2 over a coin at u1 . Now let the starting positions of the
four coins be u1 , u2 , u3 , u4 . By the previous observation, every position v
reachable by jumping is in Λ(u1 , u2 , u3 , u4 ).

Conversely, is every position v ∈ Λ(u1 , u2 , u3 , u4 ) reachable? Sadly no:

if u1 = u2 = (0, 0), u3 = (0, 1), and u4 = (1, 0), then it is easy to see that
Λ(u1 , u2 , u3 , u4 ) = Z2 but (1, 1) is not reachable (this follows from the four
color argument of 1.6. So this approach does not completely work. Still,
I would try to go further along these lines if I really wanted to solve this
problem.

See what I did here? I don’t have a solution, but I still achieved some
things that might be interesting / useful: I gave a meaningful mathematical
definition that is obviously relevant to this problem (the affine lattice); I
made a non-trivial observation (every reachable point is in the lattice); I
made a plausible conjecture (every lattice point is reachable) and disproved
it by giving a counter-example (three coins in a triangle). Thus, even if you
do not solve a problem, you can still say a lot of interesting stuff about it.

6
2 Exclusion-Inclusion
2.1 Sets
Exercise 2.1. Let A, B, C be finite sets.
1. Prove that |A ∪ B| = |A| + |B| − |A ∩ B|.
2. What about |A ∪ B ∪ C|? Find a formula in terms of pairwise and
three-wise intersections.
3. What about |A ∪ B ∪ C ∪ D|? Find a formula in terms of pairwise,
three-wise, and four-wise intersections.

Exercise 2.2. [The Exclusion-Inclusion Formula] Maybe you have noticed a

T formula, i.e., for |A1 ∪ · · · ∪ An | in terms of the size
pattern. Find a general
of intersections AI := i∈I Ai .

X
|A1 ∪ · · · ∪ An | = (−1)|I|+1 |AI | .
∅6=I⊆[n]

Exercise 2.3. Justify the formula you found in the previous exercise. Hint.
There is a proof using induction on n. Hint. There is a proof that does not
need induction on n.

Proof. Let S := A1 ∪ · · · ∪ An . For x ∈ S and a set A, let [x ∈ A] be an

P which is 1 if x ∈ A and 0 if x 6∈ A. For a set A ⊆ S it holds that
expression
|A| = x∈S [x ∈ A]. Thus, we can re-write the inclusion-exclusion formula
as
" #
X X X \
1= (−1)|I|+1 x ∈ Ai .
x∈S x∈S ∅6=I⊆[n] i∈I

We claim that equality holds for every element x. That is, we claim that for
every x ∈ S,
" #
X \
(−1)|I|+1 x ∈ Ai = 1 .
∅6=I⊆[n] i∈I

7
 Indeed, for a fixed element x ∈ S, let J :=T{i ∈ [n]
 | x ∈ Ai }. Since
x ∈ S, this set J is non-empty. Note that x ∈ i∈I Ai is 1 if I ⊆ J and 0
otherwise. Therefore,
" #
X \ X
(−1)|I|+1 x ∈ Ai = (−1)|I|+1
∅6=I⊆[n] i∈I ∅6=I⊆J
X
=1+ (−1)|I|+1
I⊆J
X
=1− (−1)|I|
I⊆J

The sum in the last expression is the number of even subsets of J minus the
number of odd subsets of J. We know from the lecture (or from the binomial
theorem) that this is 0.

3 Feasible Intersection Patterns

Exercise 3.1. Find sets A1 , A2 , A3 , A4 such that all pairwise intersections
have size 3 and all three-wise intersections have size 1. Formally,
1. |Ai ∩ Aj | = 3 for all {i, j} ∈ [4]


2
,

2. |Ai ∩ Aj ∩ Ak | = 1 for all {i, j, k} ∈ [4]

3
.
Note that there was a typo in the earlier version, as I wrote |Ai ∩ Aj | = 2.
It should be |Ai ∩ Aj | = 3, as in the preceding text.
We define
[
Ai := ([4] \ {i}) ∪ {{i, j}} .
j6=i

So Ai consists of three numbers and three size-two sets of numbers. For

example, A1 = {2, 3, 4, {1, 2}, {1, 3}, {1, 4}}. For a pair {i, j} we have {i, j} ∈
Ak if and only if k ∈ {i, j} and thus a three-wise intersection contains no
pairs and exactly one number, namely Ai ∩ Aj ∩ Ak = [4] \ {i, j, k}. As for
two-wise intersections we get
Ai ∩ Aj = ([4] \ {i, j}) ∪ {{i, j}} ,
which has size 3. For example, A1 ∩ A2 = {3, 4, {1, 2}}.

8
Exercise 3.2. Show that if we insist that |Ai | = 5 for all i, then the task
from the above exercise cannot be solved.

We write Aij as a shorthand for Ai ∩ Aj and Aijk = Ai ∩ Aj ∩ Ak and so

on. By exclusion-inclusion, we can bound |A1 | from below as follows:

|A1 | ≥ |A12 ∪ A13 ∪ A14 |

= |A12 | + |A13 | + |A14 | − |A123 | − |A124 | − |A134 | + |A1234 |
= 3 · 3 − 3 · 1 + |A1234 | ≥ 6 .

In the spirit of the previous questions, let us call a sequence (a1 , a2 , . . . , an ) ∈

N0 feasible if there are sets A1 , . . . , An such that all k-wise intersections have
size ak . That is, |Ai | = a1 for all i, |Ai ∩ Aj | = a2 for all i 6= j and so on. The
previous exercise would thus state that (5, 3, 1) is not feasible, but (6, 3, 1)
is, as one solution of Exercise 3.1 shows.
This is a typo. The length of the sequence, n, has to be the same as the
number of sets. Thus, the previous exercise shows that (6, 3, 1, 0) is feasible
and (5, 3, 1, 0) and (5, 3, 1, 1) are infeasible. Sorry for the confusion.

**Exercise 3.3. Find out something interesting about feasible and infeasible
sequences.

It turns out that this problem becomes simpler if we T make it more general.
For a sequence of sets A1 , . . . , An we write AI := i∈I Ai . This notation
makes sense for ∅ = 6 I ⊆ [n]. Note that A{i} = Ai . We define the intersection
ensemble of A1 , . . . , An to be (aI )∅6=I⊆[n] , where I is defined as

aI := |AI | .

That is, aI is the number of elements x that are in every set Ai , i ∈ I.

Formally, the intersection ensemble is a function from 2[n] \ {∅} into N0 ,
telling us, for each I, the size of the corresponding intersection. For example,
consider the following set sequence:

9
 A1
A2

A3
Its intersection ensemble would be
I {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
aI 3 4 3 1 1 2 1
Note that in the previous scenario we require aI to be the same number
for all sets of a common size k. This is not the case here: a{1,3} 6= a{2,3} .
Still, we can define aI for general set sequences. We can now ask the more
general question:
Suppose we are given a number n ≥ 1 and an ensemble
(aI )∅6=I⊆[n] of numbers. How can we determine whether there
a sequence of sets A1 , . . . , An such that aI = |AI |?
Often it turns out that questions become easier to answer if you slightly
change a definition. For A1 , . . . , An and ∅ =
6 I ⊆ [n] define
!  
\ [
BI := Ai \  Aj  .
i∈I j∈[n]\I

These are the elements that are in all Ai , i ∈ I but not in any further Aj .
We define the exclusive intersection ensemble of A1 , . . . , An to be (bI )∅6=I⊆[n] ,
where bI := |BI |. For example, the exclusive intersection ensemble of the
above picture would be
I {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
aI 2 2 1 0 0 1 1
Read this as follows: one element is in A2 and A3 but not in A1 , thus b{2,3} =
1. No element is in A1 and A2 but not in A3 , thus a{1,2} = 0. Now we ask
which ensembles (bI )∅6=I⊆[n] are feasible, i.e., are the exclusive intersection
ensemble of a set sequence A1 , . . . , An . It turns out: all are.

10
Theorem 3.4. Let n ≥ 1. An ensemble (bI )∅6=I⊆[n] is feasible (i.e., it is the
exclusive intersection ensemble of some A1 , . . . , An ) if and only if all bI are
non-negative integers.
Proof. First suppose that the condition is obviously necessary: if some bI is
not integer or is a negative integer, this sequence is clearly not feasible. To
show that it is sufficient, let us directly construct a set sequence A1 , . . . , An :
For every non-empty I ⊆ [n] we create bI many elements. Let us call those
elements (I, 1), (I, 2), . . . , (I, bI ) for concreteness. We add these elements to
every Ai where i ∈ I but to no other Aj . Thus clearly
! !
\ [
BI = Ai \ Aj = {(I1 ), . . . , (I, bI )} ,
i∈I j6∈I

which has size bI . All in all, we can write Ai as

[
{(I, 1), (I, 2), . . . , (I, bI )} .
I⊆[n]:i∈I

This shows that (bI )∅6=I⊆[n] is feasible.

Given such a b-ensemble, can we compute the a-ensemble? Can we com-
pute the aI given the bI ? Of course we can:
S P
Lemma 3.5. AI = J⊇I BJ and thus aI = J⊇I bJ .
Here, “J ⊇ I” is a shorthand for “J ⊆ [n] : J ⊇ I”. Should we prove
the lemma? I guess it is pretty obvious: first of all the sets BJ are pairwise
disjoint Now fix some x ∈ AI and define Jx := {i ∈ [n] | x ∈ Ai . Then Jx ⊇ I
and x is contained in BJx .

Now that we have (somehow informally) proved the lemma, can we com-
pute the bI when given the aI ? That is, can we “invert” the sum of Lemma 3.5?
Well, obviously A[n] = B[n] . How about A[n−1] = A1 ∩ · · · ∩ An−1 ? This is
B[n−1] ∪ B[n] and thus b[n−1] = a[n−1] − bn = a[n−1] − a[n] . Playing around a
little bit more we see that bI is a sum of the aJ with some “−” and some
“+”. Some sharp observation leads us to conjecture the following “inversion
formula”:
Lemma 3.6. bI = J⊇I (−1)|J\I| aJ .
P

11
Proof. Let us start with the right-hand side and plug in our formula for aI
in terms of bI . We get
X X X
(−1)|J\I| aJ = (−1)|J\I| bK (by Lemma 3.5)
J⊇I J⊇I K⊇J
X
= (−1)|J\I| bK
J,K⊆[n]:I⊆J⊆K
X X
= bK (−1)|J\I| .
K⊇I I⊆J⊆K

Let me pause here. The notation “I ⊆ J ⊆ K” means we sum over all J

that are a superset of I and a subset of K. Note that I has a fixed meaning
in the calculation above (i.e., it is never a summation index), whereas K is
the summation index of the outer sum, thus in the inner sum it has a fixed
meaning. What we are doing here is changing the order of summation. This
is a very common method in maths. Becoming fluent in switching orders of
summation and summation indices will help you a lot.
Next, we perform a change of summation index: Note that instead of
summing over all J with I ⊆ J ⊆ K, we could just as well sum over all
X ⊆ K \ I and get J as J = I ∪ X. Note that |J \ I| = |X| with this
notation. The above double sum becomes
X X X X
bK (−1)|J\I| = bK (−1)|X| .
K⊇I I⊆J⊆K K⊇I X⊆K\I

Look at the inner sum: it is the number of even subsets of K \ I minus the
number of odd subsets. We know that this is 0 from the lecture. Except one
important special case: if K \ I = ∅ then it has one even subset (the empty
set) and no odd subset. In this case, the inner sum is 1. Note that K \ I
happens exactly once, namely for K = I. Thus, the inner sum is 1 for K = I
and 0 for all other K ) I. We conclude that
X X
bK (−1)|X| = bI .
K⊇I X⊆K\I

This is exactly what we wanted to prove.

Good, but how do we solve the original problem: given a sequence (a1 , . . . , an ),
is it feasible? Well, we think of (a1 , . . . , an ) as an “abbreviated version” of

12
(aI )∅6=I⊆[n] that takes into account that |AI | = ai for all I of size i. By the
inversion formula we obtain
X
bI = (−1)|J\I| aI
J⊇I
X
= (−1)|J\I| a|I| (aI depends only on |I|)
J⊇I
n  
X
j n−i
= (−1) aj .
j−i
j=|I|

The last equality follows since for every j, the number of sets J ⊇ I having
n−i


size j is j−i : of the j elements, i are already fixed, since J contains all of
I; the remaining j − i elements must be chosen from the n − i elements of
[n] \ I. Thus, we arrive at the following equation:
n  
j n−i
X
bi = (−1) aj .
j=i
j−i

We are now ready to state our main result:

Theorem 3.7. The sequence a1 , . . . , an is feasible if all ai are integers and

n  
X
j n−i
(−1) aj ≥ 0 (1)
j=i
j−i

for every i ∈ [n].

Note that one can easily check the criterion of (1), for example by writing
a short computer program. Thus, we have an efficient way of determining
whether a given sequence is feasible or not.

13