jump to navigation

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 #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 #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 #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 #418: Not Cupcake Flour December 29, 2012

Posted by Saketh in : potd , add a comment

Snickers sells pastry flour. She fills orders by using a balance and a set of $9$ rocks to weigh the bags. Each rock weighs an integer number of pounds, and all of the rocks have distinct weights.

By placing some subset of the rocks on one side of the balance, Snickers can measure any integer weight between $1$ and $500$ pounds, inclusive. How many distinct sets of rocks could she have?

Problem of the Day #415: Penny Flipping December 27, 2012

Posted by Saketh in : potd , add a comment

Yuqing is playing with a triangle of pennies, similar to those shown below.

pennytriangle

The triangle is of unspecified size, but we know that all but one of the pennies is initially heads up (with the last being tails up). He can manipulate the pennies by flipping any entire row, or by rotating the whole triangle $120^{\circ}$.

Yuqing wants to turn all the coins tails up. Determine, for all triangle sizes, all positions for the coin that is initially tails up such that it is possible for him to do so.

Problem of the Day #408: Rolling Dice April 30, 2012

Posted by Alex in : potd , add a comment

Find the expected number of rolls of a fair six-sided die before the sequence of rolls contains $1, 2, 3, 4, 5, 6$ (in that order) as a subsequence.

Problem of the Day #407: Cow Tipping April 29, 2012

Posted by Saketh in : potd , 1 comment so far

Alex is going cow-tipping! Each cow he encounters is shaped like a cube, and has each edge and face colored either black or white. As an exceptionally skilled cow-tipper, Alex knows that many seemingly different cows are not rotationally distinct. How many different cow colorings are there?

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 #395: Dessert April 17, 2012

Posted by Saketh in : potd , add a comment

Alex just had a sumptuous dinner at his favorite restaurant. He now has $n$ different choices for dessert.

With so many good options, he decides to pick randomly using a coin. However, he wants to ensure that each dessert has an equal probability of being picked.

Devise a strategy for choosing dessert that minimizes the expected number of flips needed, and express the expected number in terms of $n$.

Bonus: Now solve the same problem in the case that Alex’s coin is weighted to land heads more often than tails.