| [ QuizWit ] in KIDS 글 쓴 이(By): hongcho (홍이) 날 짜 (Date): 2008년 09월 05일 (금) 오전 06시 38분 56초 제 목(Title): Re: CACM August 2008 "Puzzled" Column 답이 길군요... 담부턴 안 올리렵니다. -_-; 그냥 고대로 옮겨적습니다. 1. Election Year To prove that the opinions eventually become fixed or cycle every other day, think of each acquaintanceship between citizens as a pair of arrows, one in each direction. Let us say an arrow is currently "bad" if the party of the citizen at its tail differs from the next-day's party of the citizen at its head. Consider the arrows pointing out from citizen Clyde on day _t_, during which (say) Clyde is a Democrat. Suppose that _m_ of these arrows are bad. If Clyde is still (or is again) a Democrat on day _t+1_, then the number _n_ of bad arrows pointing toward Clyde at day _t_ will be exactly _m_. If, however, Clyde is a Republican on day _t+1_, _n_ will be strictly less than _m_ since it must hae been that the majority of his friends were Republican on day _t_. Therefore a majority of the arrows out of Clyde were bad on day _t-1_, and now only a minority of the arrows into Clyde on day _t_ are bad. The same observations hold if Clyde is a Republican on day _t-1_. But, here's the key: Every arrow is out of someone on day _t-1_ and into someone on day _t_. Thus, the total number of bad arrows cannot increase between days _t-1_ and _t_; in fact, that number will go down unless every citizen had the same opinion on day _t-1_ as on day _t+1_. But the total number of bad arrows on a given day cannot decrease forever and must eventually reach some number _k_ from which it never descends. At that point, every citizen will either stick with his or her party forever or flop back and forth every day. The puzzle can be generalized considerably by, for example, adding weights to vertices (meaning some citizens' party memberships are more prized than others), allowing loops (citizens who consider their own current opinions as well), and allowing tie-breaking mechanisms and even different thresholds for party changes. [Source: This puzzle was suggested to me by Sasha Razborov of the Institute for Advanced Study in Princeton, NJ, who says it was considered for an International Mathematics Olympiad but rejected as too difficult. It was posed and solved in a paper by Goles, E. and Olivos, J. Periodic behavior of generalized threshold functions. _Discrete Mathematics 30_ (1980), 187-189.] 2. Island of Foosgangland Suppose there are _n_ intersections and _m_ paths in Foosgangland; we may assume the paths are numbered _1_ through _m_. Since each path has two ends, the average number of paths meeting at an intersection is _2m/n_. Let us place a pedestrian at every intersection. At time _1_, the pedestrians at each end of path _1_ change places, giving a friendly wave as they pass each other in the middle of the path. At time _2_, the pedestrians currently at each end of path _2_ change places. This continues until at time _m_, the pedestrians who find themselves at each end of path _m_ change places. What has happened here? Observe first that every one of the _n_ pedestrians has taken an "increasing walk"; that is, he or she has walked a path, rested, then walked a higher-numbered path, and so forth. Since every edge has been traversed twice, the total length of all these walks is _2m_. But then the average length of the walks is _2m/n_, and it follows that at least one of the paths has length at least _2m?n_, and we are done. [Source: This puzzle and its elegant solution were passed to me by Ehud Friedgut of the Hebrew University of Jerusalem. We traced the puzzle back to the fourth problem in the second round of the 1994 Bundeswettbewerb Mathematik, one of two major German mathematical competitions.] 3. Graph Coloring Game This puzzle remains unsolved as of this writing. We have no idea how to go about it. The usual approaches (such as symmetrization, strategy stealing, and induction) don't seem to work. But surely it should be true, don't you think? 홍 (bj0219/bi0237/at0040/ar0148/ap0140/ao0326/an0263/am0028). |