ashani.dasgupta@cheenta.com

3 new problems

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

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

How many regions are created in this process?


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *