| |
|
|---|
A solution and a new problem is posted late Monday evening each week during fall and spring semesters at www.cs.colostate.edu/~rmm/mathChallenge
One winner from Fort Collins each week is eligible for two free Cold Stone Originals with three toppings each, courtesy of the Cold Stone Creamery on Laurel one half block west of College in Fort Collins. A link to our site has recently been picked up by the ACM SIGACT webpage. To accommodate solvers from other cities, we will begin to add harder problems worth a $50 gift certificate to Barnes and Noble, redeemable anywhere in the U.S., to one correct solver a week.
Email your solutions to solution@math.colostate.edu. Indicate your status (undergrad/grad/faculty/other) and school affiliation or city of residence if you are not affiliated with a school. If you are from another town, indicate whether you can make use of the ice cream.
Email ideas for future challenges to Ross McConnell (rmm@cs.colostate.edu)
For the ice cream: A jailer in charge of prison cells 1 through n gets drunk one night when the prisoners are asleep. He goes down the row opening unlocking every cell. Then he goes back down the row re-locking the even-numbered cells. Then he goes back down the row turning the locks of cells {3, 6, 9, ...,}, locking each one that is unlocked and unlocking each one that is locked. Then he goes back down turning the locks of cells {4,8,12,...,}, locking each one that is unlocked and unlocking each one that is locked, etc. After he has done this n times, he goes to bed.
In the morning, the prisoners wake up, and the lucky ones who find their cells unlocked escape. Who are the lucky ones?
Correct solutions were submitted by Jesse Snyder, Adrianna Casillas Chris Hoover (CSU undergrads), Chris Hoover, Lashi Dodge, Jilmil Saraf, Yao Jianyi, Toan Nguyen, Saravan Sellappa (CSU grad students), Byung-Soo Kim (South Korea), Lou Cairoli (Cleveland), Natalia Ryabova (grad student, Universitaet Rostock). Jesse wins the ice cream. Congratulations to all solvers.
For the $50 Barnes and Noble certificate (Contributed by Alexander Hulpke, CSU Math Department): If you place n red points in the plane, they can form as many as n-choose-3 triangles. Show that for every set of n red points in the plane, you can place 2n blue points so that every one of the triangles formed by the red points has a blue point in its interior.
Charlie Ross (CSU grad student) was the only solver with a correct proof and won the $50 Barnes and Noble certificate. Congratulations, Charlie!
For the ice cream: You can cut a piece of cheese into two pieces with one straight cut, four pieces with two cuts, and eight pieces with three cuts. It's not hard to see that you can only cut it into 15 pieces with four cuts. (Unlike last week's problem, you aren't allowed to rearrange the chunks of cheese between cuts.) What's the greatest number of pieces can you cut it into with five straight cuts? This seems almost impossible to visualize, but there is a surprisingly easy way to look at it and find the answer.
Correct solutions were provided by Monica Chawathe (CSU grad) Scott Dansford (School of Mines), Byungsoo Kim (South Korea). Byungsoo, who will be coming to Fort Collins soon, gets the ice cream. Note the similarity of the solution we have given and Pascal's triangle. Here is a nice solution provided by Lou Cairoli of Cleveland that takes advantage of this relationship.
For the Barnes and Noble certificate: Given a simple cycle C in an undirected graph, a shortcut across the cycle is an edge that is not part of the cycle, but whose endpoints are part of the cycle. A cycle is empty if it has size greater than three and no shortcuts. Filled graphs are those graphs that have no empty cycles anywhere in them.
You have a large graph with n vertices and m edges, and it is vital for you to know whether it is a filled graph. You meet a pirate who has a patch over one eye, a peg leg, and an interest in graph theory. He claims that he has checked your graph and found out that it is not a filled graph. He has a reputation for dishonesty, but to prove that he's not lying, he points out what he claims are the vertices of a large empty cycle of size c in cyclic order.
Give as good a big-O bound as you can, in terms in n, m, and/or c, on an algorithm for either concluding with certainty that the graph is not a filled graph, or concluding with certainty that the pirate has passed you a phoney proof. Your algorithm must be impossible to fool, even if the pirate is clever. There is a surprisingly efficient algorithm for the problem.
You may assume that your graph is represented with any standard generic graph representation, such as a boolean matrix.
Correct analyses were given by Ben Joeris (Fort Collins High) and Jilmil Saraf and Saravana Sellappa (CSU grads), who gave O(m) solutions, Kyle Thayer (CSU undergrad), who gave an O(c^2) solution, Mark Roberts (CSU grad), who derived both of these bounds, and Byungsoo Kim, who gave an O(m^3) solution. The coup de grace was delivered by Scott Lundberg, CSU undergrad, who gives the O(n) bound described in the posted solution.
For the ice cream: You must slice a 3-by-3-by-3 cube of cheese into 27 1-by-1-by-1 cubes. It is easy to see how to do this with six slices: two in each direction. Find the minimum number of slices it takes if you are allowed to stack pieces you've already cut and count an entire cut through the stack as a single cut. Prove that your answer achieves the minimum possible number of cuts.
Correct solutions were submitted by Ben Joeris (Fort Collins High), Yao Jianyi, Daegon Kim, Toan Nguyen (CSU grad students), Stew Crawford (CSU alum), Lou Cairoli (Cleveland), Steve La Fleur (University of Nevada, Reno), Natalia Ryabova (Universitaet Rostock), Byung-Soo Kim (South Korea), Florian Hulpke, Universitaet Hannover. Jilmil Saraf (CSU grad student) did not give a formal proof, but claims she has enough pieces of cheese in her kitchen to convince anybody of the correct conclusion. Toan wins the ice cream.
For the Barnes and Noble Certificate: A professor has to make a cross-country car trip. He must fill his tank with gas at least every i miles and must visit a restroom at least every j miles. Some of the stops along the way are roadside rest areas that have restrooms but no gas. Some are gas stations where the restrooms are out of order. Some gas stations have both gas and working restrooms. He has a map that details all of this information for the n possible stops along the route.
Come up with an algorithm that finds the minimum number of stops he has to make. A stop at a gas station that has working restrooms only counts as one stop. Give the best big-O time bound that you can for the problem.
Ben Joeris, a senior at Fort Collins High, gave the only complete solution to this problem and an O(n^2) bound. Ben wins the Barnes and Noble certificate.
The problems again: Three pirates captured a bag of gold which held between two hundred and three hundred identical coins. They agreed that when they got to port the next day they would divide the gold evenly amongst themselves. That night the first pirate sneaked into the storage room, divided the gold into three piles and had one coin left over, which he tossed overboard. He took one-third of what remained and put the rest back into the sack.
Later that night pirate two sneaked into the storage room, divided the coins into three equal piles and had one coin left over, which he tossed overboard. He took what he thought was his one-third share and put the remainder back in the sack.
Towards morning pirate three repeated the same strategy, dividing the gold into three equal piles and tossing the one remaining coin overboard. then he took his one-third and put the remaining coins into the sack.
Later in the day they took the sack of coins to the harbourmaster, asking him to divide the coins for them. He divided the coins into three equal piles and had one coin left over, which he kept as his payment.
For the ice cream: Determine many coins were in the sack to begin with.
For the Barnes and Noble certificate: Determine a solution for the general n-pirate problem. That is, there are n pirates, each visits the room once, divides the remaining coins into n piles, one coin is left over and gets tossed overboard, and he leaves with what he thinks is his share. The next day, the harbourmaster divides the remaining coins and keeps one as his fee.
Hint: A particularly nice solution works by reducing the problem to the following lawyer problem:
There are n lawyers. Each lawyer enters and takes a fraction 1/n of the coins remaining in the room. Unlike a pirate, no lawyer would ever consider throwing away a coin. They don't need to, because the number of coins remaining at each visit is divisible by n. After the n lawyers have visited, the law firm divides what is left equally among n partners, leaving nothing left over for the client.
People who solved the ice-cream version were Toan Nguyen, Priya Venkataraman, Jilmil Saraf (CSU grad students).
People who solved the general problem (hence the ice-cream version as a special case): Scott Lundberg, Chris Hoover (CSU undergrads), Saravana Sellappa, Kyriakos Chatzidimitriou, Daegon Kim, Yao Jianyi, Cliff Jones (CSU grad students), Julien Gaigneur (Heidelberg), and Byungsoo Kim (South Korea). Kyle Thayer (CSU undergrad) came up with a more complicated expression involving a summation. Daegon wins the ice cream and Julien wins the Barnes-and-Noble certificate.
Lou Cairoli of Cleveland solved the ice-cream version, then wrote back to point out a web site that had a solution to the general problem: mathworld.wolfram.com/MonkeyandCoconutProblem.html. See if you think that the reduction to the lawyer problem is an easier approach.
Quote of the week: ``To understand recursion, you need to understand recursion.'' (Dave Knopp, Denver.)
A policeman is trying to track down a thief on a bicycle. He comes upon a muddy street and sees the thief's wobbly tire tracks through the mud. How can he tell which direction the thief was traveling? Click here to see a picture of the thief's bicycle.
We have modified our statement of the problem from last week, when we stated that the policeman came upon a muddy spot in the street with the thief's tracks in it. Hats off to Shawn Pocotte (CSU undergrad), Monica Chawathe (CSU grad), Steve La Fleur (University of Nevada, Reno) for catching us off guard with a solution we hadn't expected: look at which side of the muddy patch has dirt tracked out of it! Scott Danford (Colorado School of Mines), Florian Hulpke (Universitaet Hannover), and Lou Cairoli (Cleveland) came up with the solution we give here. Also, note Lou's April Fool's joke mentioned in the solution. Scott wins the ice cream.
It is well-known that if you are lost in a maze of rooms and hallways and have a large bag of coins in your possession, you can use the coins to mark where you've been and find your way out. For details, click here.
We at CSU are cheap, and we don't like that algorithm. We don't want to leave any more money behind for the maze janitor than we have to. We want an algorithm that minimizes the amount of money left behind. (We don't think that the problem has been posed in the literature, and we happen to know that there is a surprisingly good solution.) If you find a good solution, we can name it the "CSU Tight-Wad Algorithm" in honor of our school. However, if one of our solvers from another school comes up with a cheaper algorithm than yours, we will be forced to name it after their school instead. Note that Scott Danford of Colorado School of Mines won the ice cream last week.
Solutions that left no coins behind were given by CSU grad students Li Hua, Yao Jianyi, Kyle Thayer, Daegon Kim, Mark Roberts, Cliff Jones, as well as our fellow tight-wads Zach Roth (undergrad, Hastings College) and Natalia Ryabova (grad student, Universitaet Rostock). Let's christen it the CSU-Hastings-Rostock algorithm. Cliff wins the ice cream this week.
Correct solutions were submitted by Li Hua, Daegon Kim, Aggie Chadraa, Yao Jianyi (CSU students), Nick Krier (CSU faculty), Scott Danford (grad student, Colorado School of Mines), Natalia Ryabova (grad student, University of Rostock, Germany), Lou Cairoli (Cleveland). Scott wins the ice cream. Congratulations to all solvers.
At 8:00 a.m., Alice starts out on a bicycle from town A, headed for town B. At the same moment, Bob starts out on a bicycle from town B, headed for town A. Each of them travels at a constant rate, and they pass each other at 10:00 a.m. Each of them stops for a half hour at their destination to eat lunch, and then begins the return trip at the same rate. They are now passing each other again, 45 minutes after Bob finished lunch. What time is it?
Correct solutions were given by Jianyi Yao, Troy Butler, Andres Alavarez, Li Hua, Chris Hoover, Priya Venkataraman, Monica Chawathe, Will Hickey (CSU students), Scott Danford (Colorado School of Mines student), Nick Krier (CSU faculty), Lou Cairoli (Cleveland), Florian Hulpke (student, University of Hannover). Yao gets the ice cream. Congratulations to all solvers.
The problem: There is a three-storey building consisting of a 3-by-3 arrangement of rooms on each floor. Whenever two rooms share a wall, there is a doorway between them. Whenever two rooms share a ceiling/floor, there is a spiral staircase between them. You are in a corner room on the ground floor. Try to give an itinerary that visits all rooms of the building and ends in the center room of middle floor, without backtracking through any room. If this is impossible, prove it.
Correct colutions were given by Kyle Thayer (CSU undergrad), Saravana Sellappa, Daegon Kim, Kyriakos Chatzidimitriou (CSU grad students), Lou Cairoli (Cleveland), Joh Madden (Denver). Joh wins the ice cream.
This problem is a nontrivial variant of Challenge 5, and the solution to Challenge 5 gives a hint about how to solve it.
Three hundred sixty caterpillars are placed at random initial positions on a 100-meter wire that makes a circular loop. Each caterpillar is initially facing the clockwise direction or the counterclockwise direction, and this is also determined randomly. Each caterpillar crawls at the rate of 100 meters per hour along the wire, but turns around and starts crawling the opposite direction at the same rate each time it encounters another caterpillar.
What is the probability that a caterpillar will be in its exact starting position after one hour? What is the probability after 360 hours?
Correct solutions were given by Winsor Chen, Scott Lundberg (CSU undergrads), Kyriakos Chatzidimitriou, Saravana Sellappa, Daegon Kim (CSU grad students), Rocke Verser (Loveland), Lou Cairoli (Cleveland), Florian Hulpke (Grad student, University of Hannover). Rocke Verser, who has submitted many beautiful solutions to our challenges, wins the ice creams this time. Incidentally, here is a link about Rocke's role in breaking the RSA DES challenge in 1997.
The problem again: There are 100 caterpillars placed randomly on a 100-meter wire. Each caterpillar is initially facing end A or end B of the wire; this is also determined randomly. Each caterpillar crawls at the rate of 100 meters per hour along the wire. When a caterpillar meets another or reaches an end of the wire, he turns around and starts crawling the opposite direction.
What is the chance that a randomly selected caterpillar will be in his initial position and orientation after exactly one hour? What is the chance after exactly two hours? (You may neglect the effect of the length of a caterpillar by assuming that they have length 0 or that they turn around when their midpoints cross.)
Addendum: If you prefer, answer the following nicer but more difficult variant of the problem. To the above arrangement, add another caterpillar, Alice, to the exact middle of the wire. What is the probability that after one hour, Alice is at the exact middle again? How about after two hours?
Correct solutions were submitted by Scott Lundberg (CSU undergrad student), Daegon Kim, Kyriakos Chatzidimitriou, Li Hua (CSU grad students), Rocke Verser (Loveland), and Lou Cairoli (Cleveland). Daegon wins the ice cream. Congratulations to all solvers!
The problem: Administrative and faculty numbers on a college campus have four digits and 0000 is not permitted as a telephone number. Show that if there are 5001 numbers in use, then no matter how they're assigned, it is impossible to avoid having two people's numbers that add up to a third person's number.
The problems again: Last week's problem shows that you can determine which one of 12 coins is counterfeit using three weighings of a balance scale, provided that the counterfeit coin weighs a different amount from the good coins.
Problem 1: Show that you can solve the problem even if you are required to specify in advance which coins will be placed in which trays in each of the three weighings, before you have seen the results of the first weighing! To make it easier, let us assume that you are allowed access to 12 additional coins that are known to be good. You are allowed to mark the coins with numbers without affecting their weights.
Hint: Consider the representations of the integers from 1 to 12 in base 3.
The solution to Problem 1 is a variant of a solution to last week's problem that we were astonished to get from Chris Hoover, a C.S. undergrad, that meets these requirements and does not make use of any trusted coins! The solution can be generalized to more coins and more weighings.
Problem 2: Find a solution to Problem 1 that does not make use of any initially trusted coins. Then show that, in k weighings, you can solve the generalization where you have the floor of ((3^k)/2 - 1) suspect coins, no trusted coins, and must specify in advance which coins go in which trays in each of the weighings.
Scott Lundberg, CSU undergrad, Priya Venkataraman, CSU grad student, and Nick Krier (CSU faculty) got solutions to Problem 2 for the case of k=3. They each get an ice cream.
Correct solutions were submitted by Chris Hoover, Ethan Twisdale (CSU undergrads), Saravana Sellappa, Priya Venkataraman, Kyriakos Chatzidimitrio (CSU grad students), Balaji Rajagopalan (C.U. Boulder faculty), Leaf Woods (other), Lou Cairoli (Cleveland). Ethan wins the ice cream.
Here is a warmup for this week's challenge. You have eight gold coins, but one of them is a counterfeit and weighs less than the others. You have an old-fashioned balance scale with two trays. A weighing consists of putting coins in the two trays and then seeing whether they balance, and, if not, which way the scale tilts. What's the minimum number of weighings required to determine the counterfeit?
For this week's challenge, consider the case where you have twelve coins and one of them is counterfeit. The counterfeit is either heaver or lighter than the others, but you don't know which. Show how you can determine the counterfeit coin with only three weighings in the worst case.
Hints: Use the scale to rule out "suspects". Consider including non-suspects in some of the weighings. The first weighing in the solution consists of four coins in each tray.
Draw a distinction between suspects that must be heavy if they are counterfeit and suspects that must be light if they are counterfeit. In the spirit of induction, work out efficient solutions for the cases of two and three remaining suspects before you attempt the full problem.
Correct solutions were given by Chris Hoover, Scott Lundberg, Kyle Thayer
(CSU undergrads),
Priya Venkataraman, Saravana Sellappa (CSU grad students)
Geof Givens, Linda Rollins (CSU faculty), Leaf Woods, Kuntal Patel (Denver),
Nicolae Popescu (Ft. Collins). Chris gets the ice cream.
The problem again:
A classic type of logic problem concerns
an island where the natives belong to two tribes: the Truth Tellers
and the Liars. The Truth Tellers always tell the truth,
the Liars always lie.
As a warmup for the challenge, think about the following problem. You are traveling on the island and you come to a fork in the road. One fork leads to the Truth Tellers' village and one fork leads to the Liars' village. You want to go to the Truth Tellers' village. There is a native standing at the fork, but the problem is that you don't know whether he's a Truth Teller or a Liar. How can you find out which fork to take by asking him just one question?
Solution to the warmup problem
For this Challenge 1, let us assume that the natives understand English, but refuse to speak it. If asked a question, they will respond in the native language of the islanders. The only thing you know about this language is that their words for "yes" and "no" are "arg" and "zog," but you don't know which of these words has which meaning.
Under these circumstances, how can you find out which fork to take with only one question? Assume that you can only ask a yes/no (arg/zog) question.