披萨的问题

A longstanding tradition in the CC Math Department has been our 披萨的问题. 大概每个街区会在数学系发布一次, and give you a chance to win a pizza by solving a math or computer science problem. 你可以自己工作，也可以小组工作. 如果你喜欢的话，你可以用计算器甚至电脑. 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. 你可以把你的解决方案变成TSC 209的Paraprofs, 以及查看过去的披萨问题及其解决方案. 祝你好运!!

数论马蹄铁

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

The present rules for 数论马蹄铁 are current as of March, 1996. 然而, 我们保留在任何春季野餐时更改它们的权利, 事实上, 每年春天增加一条规则已成为惯例.

We play the game with two teams of two players each and use regulation 马蹄铁 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). 这一轮的得分取决于参数n, which is the number of 马蹄铁 that actually end up in the pit (in our games n is seldom 4).

马蹄铁最靠近木桩的队伍得2分 ^n-1 分，下一个最近的2分 ^n-2 等等....... 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 ⁿ 点. 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, 他们立即得到额外的一分. (当一个球队得到2分时，这引起了特别的兴奋.)

游戏的目标是达到15分. If a team overshoots 15, its scoring is reversed for successive rounds. 例如, 如果一支队伍达到18人, 然后下一轮得1分, 比分变成了17, 然后16，因为17是质数. One of the charms of the game is that we seem to spend as much time talking as actually throwing 马蹄铁. 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点.

但最重要的是, 我们讨论策略, endlessly pausing to compute possible scores before throwing; often it is best for a player to avoid the pit entirely, 或者是扔 内部 坑但是 外 其他的马蹄铁. A rule implemented in 1994 deducts 1 point from the score of a team if one of its members throws in any 其他 游戏坑, and players in the 其他 game who are closest in that round get to decide whether they want n=k or n=k+1 点(我.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. 然而, those who envision intercollegiate competitions in this sport have missed the point.

练习:

1. 表明不可能在一轮中赢得游戏.
2. 显示一个队伍的最大可能累积得分是46分.
3. Assume that each player has probability p of getting in the pit (with probability 0 of getting a ringer or leaner). 在一轮比赛后，一支队伍的预期得分是多少?
4. 在一轮比赛后获得所有可能的分数. 两轮比赛也是这样吗.
5. Can you describe a situation where if a player gets in the pit at all, the 其他 team wins?

凸壳槌球

凸壳槌球 (CHC) is played on a standard 槌球 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, 击中了最后一根柱子.

1. 每个球员在第一个门柱处第一次投篮. A player starts over if he hits an其他 player's ball on that first shot.
2. 让 n 是玩家的数量.
3. After the first round, a player starts with her first shot of the round. She receives an其他 shot if her ball lands within the closed convex hull formed by the n-1个球属于其他玩家. 这种额外的投篮被称为a 船体拍摄. 在一个给定的回合中，玩家最多可以获得4次炮弹射击.
4. 如果一个球员的球碰到另一个球员的球, 这名球员有义务把对方球员的球传给对方, 通过移动他的球靠近刚刚击球的球, 然后击球, 不管他有没有把脚踩在自己的球上. 用脚击球的球叫做投篮 发送照片，而没有脚的被称为 滚动送球. The sent ball must land in the closed convex hull formed by the balls of the remaining n2的球员.
   1. 如果这是成功的，玩家将获得两个额外的奖励 免费的照片，不算作炮弹射击. Note that the 免费的照片 are in addition to the Send shot, even if it is a 滚动送球.
   2. 如果发送的球没有落在封闭的凸包中, 送出的球留在原地不动, 玩家的回合结束, 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 n2的球员. This placement is made with the general agreement and discussion of the remaining players; we say that the player has been 重心.
   3. 在给定的一轮中, 一名球员只能击打另一名球员的球一次, 为了有机会获得两次免费投篮. If the given player's ball is struck again, there is no penalty, but no free shot either.
   4. If the placement of the 其他 balls on the field is such that that the closed convex hull being aimed for is unusually thin, 我们称这种情况为 凸地狱.
5. There are no 免费的照片 obtained for going through wickets, or hitting posts. 此外, 穿过一个小门, 或者击中门柱, does not clear a player to obtain more 免费的照片 by hitting a ball already stuck by the player in that round. 引用著名槌球哲学家珍·考特的话: 这都是关于船体的.
6. The theoretical maximum number of shots available to a player in a given round is as follows:
   
   

   table

   镜头类型	可用的数量
   最初的拍摄	1
   船体照片	4
   免费的照片	2*( n-1)
   滚动送球	n-1
   总计	5+3*( n-1)

7. The closed convex hull is computed by assuming that each ball is a single point, 在球的质心处休息的.
8. The centroid is computed in a geometric way, determined by the 点 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. 此外, if there are fewer than 4 players, the probability of obtaining a 船体拍摄 is 0. 这被称为 无助的定理; 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. 但是它确实违反了 科特原则 就是这样 关于船体的一切.

Web上的凸包Java小程序:

• 快速船体和蛮力算法