CS Toolkit Problem Set Problem Set # 2
Bireswar Das (Aug 2025)
Most likely, you will find solutions to all these problems on the internet. However, the
best way not to learn the subject is to simply look at the solutions. You are strongly
encouraged to spend time on each problem before referring to the solution. It is expected
that you may sometimes spend multiple days on a single problem set.
Bonus Problems: You will not be asked to write the solution to these problems in
the assignment writing session. However, Bonus problems might appear in exams or viva.
Advice: Spend time on these problems too, because if you leave these problems now, you
may not get time to solve these before exam/viva.
1 Induction
Problem 1.1. Use induction to prove that
X X X
(1−x1 ) . . . (1−xn ) = 1− xi + xi xj −. . .+(−1)r xi1 . . . xir +. . .+(−1)n x1 . . . xn .
i i<j i1 <i2 <...<ir
Problem 1.2 (Bonus). Puzzle: Suppose, there are two persons, A and B. Their foreheads
are marked with two consecutive natural numbers (Eg. A has ‘5’ written on her forehead and
b has ‘4’.) None knows the number written on their forehead but A can see B’s number and B
can see A’s number. None can talk to each other. They remain inside a room. A questioner
comes to the room after every 1 hour and asks what are their numbers. The problem can be
stated as:
P (n): n queries are required before one of A or B figure out the numbers, if the numbers are
n and n + 1.
Prove P (n)
Problem 1.3. Show that every tournament has a Hamiltonian path.
Problem 1.4 (Bonus). Let Small = {a, b, c, d, e, f } and Capital = {A, B, C, D, E, F } be
two sets. We define a simplification method on strings on the set Σ = Small ∪ Capital as
follows: If a small letter and the corresponding capital letter occur consecutively they can be
cancelled. Example daADcBbbAf eE → dDcBbbAf eE → dDcBbbAf → dDcbAf . A word
S
is called irreducible if no more cancellation can happen. We write x − → y if the word x can
be obtained from y by a sequence of simplifications.
1. Suppose w1 and w2 are obtained from w by doing just one cancellation. Show that there
S S
is w0 such that w1 −
→ w0 and w1 −→ w0 . (Hint: Induction on length of w).
S S
→ w′ and w −
2. Show that if w − → w′′ and both w′ and w′′ are irreducible then they must
be same.
Problem 1.5 (Bonus). Using induction prove AM ≥ GM ≥ HM here AM, GM, HM
stands for arithmetic mean, geometric mean and harmonic mean.
Problem 1.6. Show that any positive natural number n can be written as n = a1 × 1! + a2 ×
2! + a3 × 3! + · · · + ak × k! for some k with ai ∈ {0, 1, · · · , k}.
1
2 Logic
Problem 2.1. Let p and q be the propositions:
p : I bought a lottery ticket this week.
q : I won the million dollar jackpot.
Express each of the following propositions as an English sentence:
(a) ¬p (d) p ∧ q (g) ¬p ∧ ¬q
(b) p ∨ q (e) p ↔ q
(c) p → q (f ) ¬p → ¬q (h) ¬p ∨ (p ∧ q)
Problem 2.2. Translate these statements into English, where R(x) is “x is a rabbit” and
H(x) is “x hops” and the domain consists of all animals.
(a) ∀x (R(x) → H(x)) (c) ∃x (R(x) → H(x))
(b) ∀x (R(x) ∧ H(x)) (d) ∃x (R(x) ∧ H(x))
Problem 2.3. Determine the truth value of each of these statements if the domain of each
variable consists of all real numbers.
(a) ∃x (x2 = 2) (c) ∀x (x2 + 2 ≥ 1)
(b) ∃x (x2 = −1) (d) ∀x (x2 ̸= x)
Problem 2.4. Find a counterexample, if possible, to each of these universally quantified
statements, where the domain for all variables consists of all real numbers.
(a) ∀x (x2 ̸= x) (b) ∀x (x2 ̸= 2) (c) ∀x (|x| > 0)
Problem 2.5. Determine the truth value of each of these statements if the domain of each
variable consists of all real numbers.
(a) ∀x ∃y (x2 = y) (f ) ∃x ∀y (y ̸= 0 → xy = 1)
(b) ∀x ∃y (x = y 2 ) (g) ∀x ∃y (x + y = 1)
(c) ∃x ∀y (xy = 0) (h) ∃x ∃y (x + 2y = 2 ∧ 2x + 4y = 5)
(d) ∃x ∃y (x + y ̸= y + x) (i) ∀x ∃y (x + y = 2 ∧ 2x − y = 1)
(j) ∀x ∀y ∃z z = x+y
(e) ∀x (x ̸= 0 → ∃y (xy = 1)) 2
