Pizza Problems

A longstanding tradition in the CC Math Department has been our Pizza Problems. These will be posted in the math department roughly once a block, and give you a chance to win a pizza by solving a math or computer science problem. You can work by yourself or in a group. You can use your calculator or even a computer if you like. Sometimes it is the first solution turned in that wins the pizza; sometimes it is the best solution (whatever that means).

Pizza problems are posted in the department by our math and computer science paraprofs. You can turn your solutions into the Paraprofs in TSC 209, as well as see past Pizza Problems and their solutions. Best of luck!!

Number Theory Horseshoes

(adapted from a description by Marlow Anderson, Steven Janke and John Watkins)

The present rules for Number Theory Horseshoes are current as of March, 1996. However, we reserve the right to change them at any spring picnic, and in fact, it has become a rule to add a rule each spring.

We play the game with two teams of two players each and use regulation horseshoes and pit. A single round of the game consists of each player throwing one horseshoe, alternating from team to team (the team which is behind decides who goes first each round). The scoring of the round depends on a parameter n, which is the number of horseshoes that actually end up in the pit (in our games n is seldom 4).

A team whose horseshoe is closest to the stake receives 2 ^n-1 points, the next closest 2 ^n-2 and so on. Thus, if three players end up in the pit, the scores are 4, 2, and 1. The main exception to this rule - and one which is rarely needed in our experience - is that "ringers" receive 2 ⁿ points. Thus, for three players in the pit with one ringer, the scores are 8, 2 and 1. But we also give the scoring a whimsical number theoretic twist: when a team's cumulative score is prime, they immediately get one additional point. (This causes particular excitement when a team has a score of 2.)

The object of the game is to reach exactly 15 points. If a team overshoots 15, its scoring is reversed for successive rounds. For example, if a team reaches 18, then scores 1 on the next round, the score becomes 17, then 16 because 17 is prime. One of the charms of the game is that we seem to spend as much time talking as actually throwing horseshoes. We discuss whether a horseshoe is in or out of the pit (and consequently, where its center of mass is); we discuss whether or not 1 is prime and why; and we discuss making new rules such as the recent addition of granting a "leaner" 2 ⁿ -1 points.

But most of all, we discuss strategy, endlessly pausing to compute possible scores before throwing; often it is best for a player to avoid the pit entirely, or perhaps to throw inside the pit but outside the other horseshoes. A rule implemented in 1994 deducts 1 point from the score of a team if one of its members throws in any other game pit, and players in the other game who are closest in that round get to decide whether they want n=k or n=k+1 points (i.e. they decide whether they want to count the foreign horseshoe in their scoring of the round).We hope that from this seed regional variations of our game will spring up across the land. However, those who envision intercollegiate competitions in this sport have missed the point.

Exercises:

1. Show that it is impossible to win the game in one round.
2. Show that the largest possible cumulative score for one team is 46.
3. Assume that each player has probability p of getting in the pit (with probability 0 of getting a ringer or leaner). What is the expected score for one team after one round?
4. Obtain all possible scores after one round of play. Do the same for two rounds of play.
5. Can you describe a situation where if a player gets in the pit at all, the other team wins?

Convex Hull Croquet

Convex Hull Croquet (CHC) is played on a standard croquet layout, with nine wickets, and two posts. The goal of the game is to be the first player to pass through all nine wickets in the correct order and direction, and hit the final post.

1. Each player takes a first shot from the first post. A player starts over if he hits another player's ball on that first shot.
2. Let n be the number of players.
3. After the first round, a player starts with her first shot of the round. She receives another shot if her ball lands within the closed convex hull formed by the n-1 balls belonging to the other players. Such an extra shot is called a Hull Shot. In a given round, a player may receive a maximum of 4 Hull Shots.
4. If a player's ball hits another player's ball, the player is obliged to send the other player's ball, by moving his ball adjacent to the ball just struck, and then striking his ball, with or without placing his foot on his own ball. A shot in which the foot is used is called a Send Shot, while one without the foot is called a Rolling Send Shot. The sent ball must land in the closed convex hull formed by the balls of the remaining n-2 players.
   1. If this is successful, the player receives two additional Free Shots, which do not count as Hull Shots for that round. Note that the Free Shots are in addition to the Send shot, even if it is a Rolling Send Shot.
   2. If the sent ball does not land in the closed convex hull, the sent ball remains where it lays, the player's turn is over, and the player's ball is placed by the next player at the centroid of the closed convex hull formed by the balls of the remaining n-2 players. This placement is made with the general agreement and discussion of the remaining players; we say that the player has been centroided.
   3. In a given round, a player may strike another given player's ball only once, in order to have a chance at getting the two free shots. If the given player's ball is struck again, there is no penalty, but no free shot either.
   4. If the placement of the other balls on the field is such that that the closed convex hull being aimed for is unusually thin, we call the situation Convex Hell.
5. There are no Free Shots obtained for going through wickets, or hitting posts. Furthermore, going through a wicket, or hitting a post, does not clear a player to obtain more Free Shots by hitting a ball already stuck by the player in that round. To quote that eminent croquet philosopher Jen Courter: It's all about the hull.
6. The theoretical maximum number of shots available to a player in a given round is as follows:
   
   

   table

   Shot Type	Number Available
   Initial Shot	1
   Hull Shots	4
   Free Shots	2*( n-1)
   Rolling Send Shots	n-1
   Total	5+3*( n-1)

7. The closed convex hull is computed by assuming that each ball is a single point, resting at the centroid of the ball.
8. The centroid is computed in a geometric way, determined by the points at which the balls rest. It is not a center of mass; balls resting interior to the geometric region have no affect on the location of the centroid.
9. Note that with fewer than 5 players, the probability of obtaining a Free Shot is 0. Furthermore, if there are fewer than 4 players, the probability of obtaining a Hull Shot is 0. This is known as Staab's Theorem; proof is left to the reader.
10. Possible variation: The last player to successfully pass through a given wicket should receive one Free Shot for accomplishing that. This rule's likely affect is to tighten the size of the closed convex hull. It does however violate the Courter Principle that it is all about the hull.

Convex Hull Java Applets on the Web:

• Quick Hull and Brute Force Algorithms