Scribd
Upload
4 views2 pages

Discrete Math Problems and Solutions

This document is a tutorial sheet for the course MTL 180 (Discrete Mathematical Structures) at the Indian Institute of Technology Delhi for Semester I, 2025-26, authored by instructor Biplab Basak. It contains a series of combinatorial problems that students are required to solve, covering topics such as polyhedra, distance in triangles, arrangements of fruit, and seating arrangements. Each problem is designed to challenge students' understanding of discrete mathematics and combinatorial principles.

Uploaded by

ahahaj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Discrete Math Problems and Solutions

This document is a tutorial sheet for the course MTL 180 (Discrete Mathematical Structures) at the Indian Institute of Technology Delhi for Semester I, 2025-26, authored by instructor Biplab Basak. It contains a series of combinatorial problems that students are required to solve, covering topics such as polyhedra, distance in triangles, arrangements of fruit, and seating arrangements. Each problem is designed to challenge students' understanding of discrete mathematics and combinatorial principles.

Uploaded by

ahahaj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

INDIAN INSTITUTE OF TECHNOLOGY DELHI

DEPARTMENT OF MATHEMATICS
SEMESTER I, 2025 − 26
MTL 180 (DISCRETE MATHEMATICAL STRUCTURES)
TUTORIAL SHEET 3

Instructor: Biplab Basak Date: 13/8/2025

Combinatorics

Problem 1: Prove that, in every polyhedron there is at least one pair of faces with the
same number of sides

Problem 2: Let ABC be an equilateral triangle, with |AB| = 3 units. Show that if we
select 10 points in the interior of this triangle, there must be at least two whose distance
apart is less than or equal to 1 unit.

Problem 3: A basket of fruit is being arranged out of apples, bananas, and oranges. What
is the smallest number of pieces of fruit that should be put in the basket to guarantee that
either there are at least seven apples or at least eight bananas or at least nine oranges?

Problem 4: Show that, in any set of 51 points inside a unit square, there are always three
points that can be covered by a circle of radius 1/7.

Problem 5: 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.

Problem 6: Given 101 integers from 1, 2, ..., 200, prove that there are at least two integers
such that one of them is divisible by the other.

Problem 7: Show that if n + 1 integers are chosen from the set {1, 2, . . . , 2n}, then there
always exist two integers which differ by 1.

Problem 8: A collection of subsets of {1, 2, . . . , n} has the property that each pair of
subsets has at least one element in common. Prove that there are at most 2n−1 subsets in
the collection.

Problem 9: Eight people are to be seated around a table; the chairs don’t matter, only
who is next to whom, but right and left are different. Two people, X and Y , cannot be
seated next to each other. How many seating arrangements are possible?

Problem 10: Suppose a box contains 18 balls numbered 1 − 6, three balls with each
number. When 4 balls are drawn without replacement, how many outcomes are possible,
assuming that the order in which the balls are drawn does not matter?

Problem 11: Six men and six women are to be seated around a table, with men and
women alternating.
(a) If the chairs don’t matter, only who is next to whom, but right and left are different.
How many seating arrangements are possible?

(b) What happens if the chairs matter?

Problem 12: Prove the following using combinatorics.


 
n+2
(1)(n) + (2)(n − 1) + (3)(n − 2) + · · · + (n − 1)(2) + (n)(1) = .
3

You might also like