jump to navigation

Problem of the Day #429: Beehive Management January 3, 2013

Posted by Saketh in : potd , add a comment

A local beehive has recently been facing some congestion issues. The hive is made up of $10$ different chambers, and every pair of chambers is connected by a direct tunnel that admits traffic in both directions. Sometimes, this can lead to messy head-on collisions that can really slow down travel around the hive.

In an effort to make travel more efficient, the queen has announced that all tunnels will be made one-way. If the direction of travel for each tunnel is chosen independently and at random, what is the probability that the bees can still get from any chamber to any other chamber?

Problem of the Day #428: The Jar of Numbers January 3, 2013

Posted by Saketh in : potd , add a comment

Owl has a jar of numbers. Any two numbers in the jar have a common divisor greater than one, yet the greatest common divisor of all the numbers is one. Furthermore, there does not exist any pair of numbers in the jar such that one divides the other.

Can you establish an upper bound on the number of numbers in the jar?

Problem of the Day #427: Batting Averages January 2, 2013

Posted by Saketh in : potd , add a comment

Kanga and Roo wrote software to keep track of their friend’s baseball stats. Now, they want to rank their friends by batting average.

Unfortunately, the software is a little finicky. It only responds to queries of one kind: given three players $A$, $B$, and $C$, it can report whether the statement “$A$ has a lower batting average than $B$, who has a lower batting average than $C$” is true.

If Kanga and Roo want to create a ranking of $N$ of their friends, determine the least number of queries they must make.

Problem of the Day #426: Honey Drops January 2, 2013

Posted by Saketh in : potd , add a comment

Two bears are sharing some honey they found by playing a little game. They get two pots, and divide the honey (not necessarily evenly) between the pots. Let the first pot contain $a$ drops of honey, and let the second contain $b$ drops of honey.

The game proceeds as follows. Each turn, one of the bears takes $2k$ drops of honey from one of the pots, eats $k$ of the drops, and places the other $k$ drops in the other pot. The bears alternate until no valid move is available, at which point the last bear to move wins.

For which values of $a$ and $b$ does the bear that goes first have a winning strategy?

Problem of the Day #425: The Great Ark January 1, 2013

Posted by Saketh in : potd , add a comment

In anticipation of the end of the world a couple of weeks ago, Dasith constructed a giant ark to be filled with pairs of many different kinds of animals.

To avoid things getting messy on the ark, he had all of the animals order themselves in a single queue. He required the $i^{\textrm{th}}$ pair of animals to place themselves in the queue such that they were separated by exactly $i$ other animals.

Here is an example of such an arrangement, known as a Langford pairing:

langford_pairing

Let $n$ be the total number of pairs of animals. The given example has $n=4$. Determine all values of $n$ for which a Langford pairing exists.

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 #423: Cookie Queries December 31, 2012

Posted by Saketh in : potd , add a comment

Albert is hungry. He visits a local djinn and wishes for a bottomless jar of cookies.

As always, there’s a catch. The crafty djinn marks $n$ of the cookies from $1$ to $n$ using some icing. He then arranges them in some fixed order $\pi([n])$ hidden away from Albert’s view.

Now, if Albert can name a subset $S$ of $[n]$ such that some permutation of $S$ is a contiguous subsequence of $\pi([n])$, he gets to eat $|S|$ cookies from the jar.

All queries (Albert’s choices for $S$) must be written down before any of them are processed. What is the least number of queries Albert can make to guarantee he will receive at least one cookie?

$\textbf{Bonus:}$ Determine, for fixed $n$ and $q$, the set of $q$ queries that maximizes the expected number of cookies Albert will get to eat.

Problem of the Day #422: Divergent Geometric Mean December 31, 2012

Posted by Saketh in : potd , add a comment

Can you find a convergent sequence of reals with a divergent geometric mean? Alternatively, give a proof that no such sequence exists.

Problem of the Day #421: Dim Sum Night December 30, 2012

Posted by Saketh in : potd , add a comment

Anand is eating at a Chinese restaurant with his family. He is going to order for all of them; he will submit one ordered tuple of non-negative integers $(x,y,z)$ representing the number of dumplings, spring rolls, and steamed buns he wants.

Now, well distributed orders (like $(10, 10, 10)$) are typically more satisfactory than unbalanced orders (such as $(29, 1, 0)$). After all, we don’t want everyone fighting over the lone spring roll! Let the quality $Q$ of a given order be modeled by the function $Q(x,y,z) = xyz$.

Anand knows how much his family will eat, so he wants $x+y+z = 30$. He will select a tuple $(x,y,z)$ at random from all those that satisfy this constraint. Determine the expected value of $Q(x,y,z)$, the quality of the order.

Problem of the Day #420: Billy the Baker December 30, 2012

Posted by Saketh in : potd , add a comment

Billy the baker is testing out a new secret ingredient. He makes a huge square brownie to be divided amongst three of his friends.

Billy wants feedback on small, medium, and large sizes. Taking out his knife, he cuts the brownie into $5$ pieces, and rearranges them to form $3$ smaller squares of distinct sizes. Find a way this can be done.