Instructor: Arijit Ghosh

Course: Discrete Mathematics (M.Tech CS, 2024-25)

Date: September 8, 2024
Problem Set 1

Refer to the main textbooks for this course [VLW01, MN09] for the definitions.

Question 1. Write the negation of the following:

(a) Every complete bipartite graph is not planar.
(b) If G = (v, e) is a directed graph s.t. for any two vertices u, v ∈ V at most one of (u, v)
and (v, u) ∈ E then ∃w ∈ V s.t. the number of vertices that are at distance 2 from w
is at least the number of vertices that are at distance 1 from w.
(c) There exists x ∈ R such that for every ϵ > 0 there exist Nϵ ∈ N such that for every
n ≥ Nϵ we have |xn − x| < ϵ. (Note: This is precisely the definition of convergence of
a real sequence)
(d) In each tree in the garden, we can find a branch on which all of the leaves are green.
(Hint: Write using quantifiers)

Question 2. Write the contrapositive statement:

(a) If we have good crops then either it rained well or the fertilization worked properly.
(b) If a tournament has a cycle then it must have a 3-cycle.

Question 3. Prove or disprove:

(a) A finite sum of distinct irrational numbers can never be a rational number.
√
(b) If p, q are two primes, pq is irrational.

Question 4. Check the logical equivalence of the following: (s → r) ∧ (q → r) = (s ∧ q) → r

Question 5. Check whether the following proposition is a tautology or a contradiction or

none: (p ∧ q) ∨ (¬p ∨ (p ∧ ¬q))

Question 6. (⋆) Prove that:

(a) 3n5 + 5n3 + 7n is divisible by 15, for every natural number n.
(b) If 2n − 1 is a prime, n is a prime.

Question 7. Prove that, at a party with at least 2 people, there are at least two people who
know the same number of people (not necessarily the same people), provided every person
is invited by someone who knows him.

Question 8. If [k] = {1, . . . , k} then calculate the following:

(a) The number of monotonically increasing functions from [m] to [n], where n ≥ m.
(b) The number of monotonically decreasing functions from [m] to [n], where n ≥ m.
1
Question 9. (⋆) Let p and q be two distinct primes, find the remainder when pq + q p is
divided by pq. (Hint: Little Theorem)

Question 10. The rules of double chess are exactly those of regular chess (all the pieces
and their moves are identical), except that in double chess either player (Black or White)
plays consequently two moves (instead of just one move permitted in regular chess) in each
of their alternate turns. Show that there exists a strategy for white which guarantees him
at least a tie.

Question 11. (⋆) Take any real number d ∈ R. Suppose all points in the plane R2 are
colored either red or blue. Prove that there are two points at distance d that are of the same
color.

Question 12. For any n ∈ N, prove that, the 2n ×2n checkerboard with any square removed
can be tiled by L-shaped triominos.

A L-shaped triomino

A 8 × 8 checkerboard with one square removed

Question 13. (⋆) Consider a n × n binary matrix B = (bij )1≤i,j≤n (i.e., bij ∈ {0, 1}). The
flip(i, j) operation inverts all the 2n − 1 cells of row i and column j, where inverting a cell
means replacing a 0 by 1 or vice versa. Can we get the zero matrix (where every element is
0) from B by performing flip operations?

Question 14. (⋆) Does there exist irrational numbers x and y, such that xy is rational?

Question 15. Let a1 , a2 , · · · , an be positive reals such that a1 a2 · · · an = 1. Then prove

that

a1 + a2 + · · · + an ≥ n

Question 16. n cars are placed at distinct positions on a closed track. The total amount of
fuel in all their tanks combined is exactly equal to the amount of fuel one car would consume
to make a round trip off the track (come back to its starting point). Prove that there is a
car that can make the round trip by taking fuel from all the other cars that it encounters
on this trip.
2
Question 17. (⋆) Are there integers x, y, z, t ∈ Z, such that 8x4 + 4y 4 + 2z 4 = t4 ?
Question 18. (⋆) Prove that every graph can be written as an edge-disjoint union of cycles
and trees.
Question 19. (⋆) Can there be a connected graph with more than two vertices, such that
the degrees of its vertices are mutually distinct?
Question 20. (⋆) Prove that either a graph or its complement is connected.
Question 21. Every graph with n vertices and more than n2 /4 edges must contain a
triangle.
Question 22. (⋆) State and prove the fundamental theorem of arithmetic. (Hint: Strong
induction)
Question 23. Suppose every road in West Bengal is one way. Every pair of cities is
connected by exactly one direct road. Show that there exists a city which can be reached
from every other city either directly or via at most one other city. (Hint: Think about graphs
or induct on the number of cities)
Question 24. (⋆) Let x be any real number such that x + 1
x
∈ Z. Prove that
1
xn + ∈Z
xn
for any n ∈ N. (Hint: need some strength in induction)
Question 25. There are n students in each of the three schools. Any student has altogether
n + 1 friends from the other two schools, note that friendship is a symmetric relation. Prove
that one can select one student from each school so that three selected students know each
other. (Hint: Consider the student with the maximum number of friends)
Question 26. A set C of propositions is called logically closed if it satisfies both the
following conditions:
(i) C contains all tautologies (propositions with truth tables containing only T in the
output column)
(ii) (Modus ponens) For any propositions p and q, if both p and p =⇒ q are in C, then
so is q.
If C is a logically closed set, then prove the following:
(a) If the propositions p1 , p2 , · · · , pn are in C, and (p1 ∧ p2 ∧ · · · ∧ pn ) =⇒ q is a tautology,
then q is also in C.
(b) If both the propositions p and ¬p are in C, then C contains every proposition.

Question 27. Let k be some fixed positive integer and P (n) be a mathematical statement
that satisfies the following properties:
(i) All of P (0), P (1), · · · , P (k − 1) are true;
(ii) P (n) =⇒ P (n + k), for any n ≥ 0.
Then P (n) is true for every n ∈ N.
3
Question 28. Suppose there are n ≥ 4 spies, each of whom knows a secret not known to
the others. They communicate in pairs (simultaneous communication between more than
two people is not allowed, as such gatherings among spies might get noticed and reveal their
identities) and in each communication, two spies share each other’s secrets. Show that 2n−4
communications are sufficient before each of them knows everything.
Question 29. (⋆) Suppose τ (n) denotes the number of positive divisors of an integer n ∈ N.
Prove that nτ (n) is a perfect square for all n ∈ N.
Question 30. Let k, ℓ be natural numbers. Then every sequence of real numbers of length
kℓ + 1 contains a nondecreasing subsequence of length k + 1 or a decreasing subsequence of
length ℓ + 1.
Question 31. Let the sets A1 , . . . , Am be m distinct subsets of [n]. Show that if for i ̸= j
we have Ai ∩ Aj ̸= ∅ then m ≤ 2n−1 .
Question 32. (⋆) For any natural number n, there is a nonzero multiple of n whose digits
are all 0s and 1s.
Question 33. In any set A of n ≥ 2 integers, there is a nonempty subset of A whose sum
is a multiple of n.
Question 34. A chess master who has 11 weeks to prepare for a tournament decides to play
at least one game every day but, in order not to tire himself, he decides not to play more
than 12 games during any calendar week. Show that there exists a succession of consecutive
days during which the chess master will have played exactly 21 games.
Question 35. Show that every sequence a1 , a2 , . . . , an2 +1 of n2 + 1 real numbers contains
either an increasing subsequence of length n + 1 or a decreasing subsequence of length n + 1.
Question 36. (⋆) Given k ≥ 4 points on a plane, no 3 points through a line. If any 4 points
are vertices of a convex quadrangle, then the k points are actually the vertices of a convex
k-gon.
References
[MN09] Jirí Matousek and Jaroslav Nesetril. Invitation to Discrete Mathematics, Second Edition. Oxford
University Press, 2009.
[VLW01] Jacobus Hendricus Van Lint and Richard Michael Wilson. A Course in Combinatorics. Cambridge
University Press, 2001.