I sometimes create small problems (mostly at pre-college level), to have fun. Here are three recent ones. Readers may give it a try or point out issues with problem-statement or indicate that it is trivial.

Please note that some version of these problems may exist somewhere as there is a tendency of familiar ideas to echo through the brain. May be I have read something like this somewhere in the past. At any rate, this is just some musing for fun.

**Problem 1**

A connected, directed graph is called a ‘Calcutta Graph’ if degree of every vertex is 3, each vertex has exactly two incoming edges and one outgoing edge.

Suppose G is a Calcutta Graph with n vertices. Then at most how many directed circuits can G have?

**Problem 2**

A $n \times n$ grid is made up of $n^2$ squares. In each square you are allowed to draw one diagonal. If $k$ diagonals line-up, end-to-end, then they make a path of length $k$. The figure below shows a $4 \times 4$ grid with a path of length $6$.

Find the maximum number of paths of length $2n$ in a $n \times n$ grid.

**Problem 3**

Suppose $n$ circles and $n$ (infinite) lines are drawn in the plane such that

- No three lines pass through a single point
- No three circles pass through a single point
- Every pair of circles intersect each other at two distinct points
- Every pair of lines intersect each other at one point
- Every line cuts every circle at two distinct points.

How many regions are created in this process?

## Leave a Reply