jump to navigation

Problem of the Day #424: Don’t Brute Force January 1, 2013

Posted by Albert in : potd , add a comment

Determine the number of non-isomorphic connected graphs on 6 vertices.

Problem of the Day #404: Biking Paths April 26, 2012

Posted by Saketh in : potd , add a comment

The city planning committee is laying down a set of bike trails between $n$ major attractions. They plan to submit a proposal asking for $kn$ of the $\binom{n}{2}$ possible trails to be built, where $k$ is some constant.

To accommodate athletes who wish to perform laps, the committee wants to guarantee that a cycle of length $4$ will be built. However, they don’t know which $kn$ trails will be chosen. What is the least value of $k$ for which a cycle of length $4$ will definitely exist?

Problem of the Day #392: Brandon the Bee April 14, 2012

Posted by Saketh in : potd , add a comment

Brandon the Bee is keeping watch over his hive, which is laid out in a hexagonal grid. Being a very busy bee, he has some very strict guidelines that he follows whenever he takes a tour of the grid:

  1. Brandon never steps outside the boundaries of the hive.
  2. He can only travel between adjacent cells.
  3. He must visit each cell exactly once.
  4. Cells are grouped in clusters, and he must enter and exit each one exactly once.
  5. Some cell borders are blocked off by dried honey. He cannot cross these.
  6. Brandon must start at the specified starting position.

Consider, for example, the hive shown below. Note that there are no blocked borders in this example.

beehive

Devise an efficient algorithm for finding a valid route for Brandon to take.

Problem of the Day #372: Binary Tree Path Lengths March 25, 2012

Posted by Alex in : potd , add a comment

Inspired by a problem from the 2012 TJ IOI.

The nodes in a complete binary tree of infinite height are referred to by ordered pairs $(x, y)$, where $x$ and $y$ are 0-indexed values denoting the row and the column of the nodes. The root is $(0, 0)$. Find the length of the shortest path between node $(1000, 3)$ and $(1234, 123456)$.

Problem of the Day #371: Connecting Components March 24, 2012

Posted by Alex in : potd , add a comment

Suppose we have a list of $100$ nodes. Every second, two nodes are randomly chosen and an edge is drawn in between the two nodes. What is the expected number of seconds that must elapse before the number of connected components of the graph is less than or equal to $5$?

Problem of the Day #275: Graphs with Special Cycles December 19, 2011

Posted by Alex in : potd , add a comment

An undirected, unweighted graph of $8$ nodes and each edge of the graph is part of exactly one cycle. Find the number of possible graphs.

Problem of the Day #216: Red Lines Blue Lines October 21, 2011

Posted by Saketh in : potd , add a comment

Alex takes a set of $N$ points and draws either a red line or a blue line between each pair. What is the smallest $N$ such that he will always create a closed path consisting of four segments, all of the same color?