|
Steven Byrnes
Roxbury Latin School, West Roxbury, MA
Individual Competition:
Southern Regional Winner (Georgia Institute of Technology):
Silver Medal - $3,000 Scholarship
National Winner: Gold Medal - $100,000 Scholarship
The 2003 1st place national winner ($100,000) was Steve Byrnes, a PROMYS first-year student in 2000, and a returning student in 2001.
Meet the Scholar
Steven Byrnes’ math project analyzes a class of two-player
games known as poset games. A poset (partially-ordered set) is a
mathematical object satisfying a few simple properties, and any
poset can be turned into a two-player game. Games such as these
are important to a growing field, known as discreet mathematics,
for their potential applications in a wide range of computer network
issues, such as the use of secure codes and reliable communications
across “noisy channels.”
Mr. Byrnes developed a new theorem, the Poset Game Periodicity
Theorem, which concerns general poset games: as a poset expands
in two directions, periodic patterns emerge in the associated poset
game not only in losing positions, but also in positions with any
fixed g-value (g-values are a general classification of game positions.)
Using his theorem, Mr. Byrnes was able to resolve two open conjectures
about a specific poset game called Chomp; proved several results
about the computational complexity of calculating g-values in poset
games; and gave an efficient (i.e. polynomial-time) winning strategy
for a large class of poset games.
Mr. Byrnes, a senior, was the only student in the country in 2002
to win both the US Math Olympiad and the US Physics Olympiad. He
is involved with fundraisers for the Maru a Pula School and Youth
Group. Mr. Byrnes is a member of Latonics, an a cappella group,
as well as glee club, the school musicals, jazz band, Varsity cross-country,
and Mad Puzzlers (math club). He plans to study mathematics in college
in hopes of becoming a professor and researcher.
Abstract
“Poset-Game Periodicity”
In this paper, we explore poset games, a large class of combinatorial games
which includes
Nim, Chomp, Hackendot, Subset-Takeaway, and others. We prove a general theorem
about
poset games, which we call the Poset Game Periodicity Theorem: as a poset expands
along two
chains, losing positions and positions with any fixed g-value have a periodic
pattern.
We use the theorem to (1) find polynomial-time winning strategies for a new,
large class of
poset games, (2) resolve two open conjectures about the game of Chomp, and (3)
prove several
important results about the computational complexity of calculating g-values
in poset games.
Mentor: Mr. Edward Early (former PROMYS student and counselor)
Siemens Westinghouse Competition
Siemens Foundation
(Links will open in a new window.)
| 
![]](../bb/end.png){kind=small}
![]](../bb/bend.png){kind=small}