| [ QuizWit ] in KIDS 글 쓴 이(By): hongcho (홍이) 날 짜 (Date): 2008년 08월 07일 (목) 오전 08시 34분 37초 제 목(Title): CACM August 2008 "Puzzled" Column CACM이 디자인부터 내용면에서 좀 바뀐 듯한 느낌입니다 (Queue의 영향을 많이 받은 듯). 제일 뒷 페이지의 "Last Byte" 컬럼이 퍼즐 컬럼으로 바뀌었네요. 출제자는 피터 윙클러 (Peter Winkler) 라는 수학/전산과 교수랍니다. 이번 달은 그래프 이론에 관한 문제 셋인데, 첫 둘은 답이 알려진 문제고 세번째는 open problem 이랍니다. 뭐 저한테는 다 감이 안 오던데... -_- 문제 자체가 이해가 잘 안 되는 것도 있고. 하여간, 이미 언급된 문제인지 아닌지는 잘 모르지만... 답은 다음 달 CACM에 나온데요. 1) Since this is an election year, it seems appropriate to visit that impressionable town in which, every evening, each citizen calls all his (or her) friends (always an odd number) and re-chooses his party affiliation -- Republican or Democrat -- the next day, in accordance with the majority of his friends at the time of the call. Can you show that, after a while, party affiliations will be the same on every alternate day? 2) The island of Foosgangland boasts a complex web of footpaths. Each section of path, from one intersection to the next, is identified by a different number. If you happen to take a walk in Foosgangland, the "length" of your walk is the number of path sections you traverse, and your walk is "increasing" if the path numbers you encounter are always go up. Prove that there is someplace on the island where you can take an increasing walk whose length is at least the average number of paths meeting at the intersections in Foosgangland. 3) In a graph-coloring game, a finite graph _G_ and a palette of _k_ colors are fixed. Alice and Bob alternately choose an uncolored vertax of _G_ and color it with a color not previously used on any neighboring vetex. Alice, who goes first, wins if all the vertices get colored; but if anyone gets stuck before that happens, Bob wins. (The game is described in an article -- Bartnicki, T., Grytczuk, J., Kierstead, H.A., and Zhu, X. The map-coloring game. _American Mathematical Monthly 114_, 9 (Nov. 2007), 793-803 -- that pointed out that the following question remains embarrassingly open: Are there a _G_ and a _k_ such that Alice wins on _G_ with _k_ colors, but Bob wins with _k_+1?) 홍 (at0040/ar0148/ap0140/ao0326/an0263/am0028/aj0124/ag0257). |