You reached this page through the archive. Click here to return to the archive.

Note: This article is over a year old and information contained in it may no longer be accurate. Please use the contact information in the lower-left corner to verify any information in this article.

St. Olaf students tackle tricky math

By Linnae Stole '10
March 10, 2010

(L-R) Vladimir Sotirov '12, Nathan Clement ’10 (his second win), and Mathew Deram '11 hold the trophy that illustrates the "pizza" theorem.

For the third time over the past four years, a team of St. Olaf math students has calculated their way to victory at the annual Konhauser Problemfest. After studying 10 problems during a three-hour period, Nathan Clement ’10, Mathew Deram '11, and Vladimir Sotirov '12 took first place at the event hosted by the University of St. Thomas. St. Olaf entered six teams in the contest.

The annual competition started in 1993 in memory of the late Joe Konhauser, a Macalester faculty member and active "problemist." In addition to St. Olaf, competitors include Carleton College, Gustavus Adolphus College, Macalester College, and the University of St. Thomas.

How would you fare? Check out problem No. 3 from this year's contest:
There are
n2 people, each on one square of an n-by-n chessboard. Some of them are "infected." At each step, anyone who is infected remains infected, and any healthy person with at least two infected neighbors (corners do not count as neighbors) becomes infected in the next step. Notice that if the main diagonal starts out infected, then after n — 1 steps everyone is infected. Prove that at least n squares must be infected initially to eventually infect everyone.

Solution: Consider each side of an infected square that doesn’t face another infected square. Call these contagious sides. At the end, when all squares are infected, there are 4
n contagious sides, just the sides on the edges of the board. Then look at the ways squares can combine to infect other squares. In each situation, it is clear that the number of contagious sides can not increase and will often decrease. Thus, the number of contagious sides stays the same or decreases with each generation. Thus a successful initial situation must start with at least 4n contagious sides, so there must be n initially infected squares, and the n squares down the diagonal will work.

Contact David Gonnerman at 507-786-3315 or gonnermd@stolaf.edu.