High School Student Research Conference Abstracts

Melissa Andrews, Amanda Beck, Kristina Bellis, Luke Cavagnaro, Val Centola, Greg Donnellan,
Rachel Eckert, Nicole Gonzalez, Julie Grinnell, Franz Holzinger, Leah Levine, Rachele Lingard,
Brittany Meyers, Anthony Mikiciuk, Sean Patterson, Nicole Pecoraro, Sarah Salminen,
Julia Simm, and Julie Thorpe

Greece Arcadia High School

TSP Used For Grocery Store Distribution
Supervised by Carol Oehlbeck, DCI 2001

To solve this problem we chose a chain of grocery stores and found the most efficient route between them by using Brute Force and Nearest Neighbor to connect the stores in the shortest distance, fastest time and avoiding highways. This minimizes the cost of product distribution. Map Quest (www.mapquest.com) was the source used to acquire distances and time of travel between the stores, which is the basis for all calculations.

Andrew Balliet, Bryan Bachelder, Brian Bennett, Lauren Callahan, Andrew Kengeter,
Darly Kranec, Teresa Kwiatek, Rocco Loreti, Michael Nappa, Brianna Paolicelli,
Michael Wallendjack

Delaware Valley High School

Variations of Tic-tac-toe, who controls?
Supervised by Richard Giantisco, DCI 2001

The outcome of every 2-player game is controlled by one of the two players. We have examined some variations of a popular 2-player game to try to discover who is favored each time and to try to examine patterns that would indicate how we could vary a game so that the other of the two players would be favored. The process followed was to build trees or directed paths of all cases of the most basic variations and use these as the basis of our conclusions.

Casey Campetti, Shane Clark, Colin Fiske, Erik Jensen, and Anna Smith
Monument Mountain Regional High School

Dominating a Chessboard with Queens
Supervised by Kathy Erickson, DCI 2001

The goal of this research project is to determine the minimum number of queens required to threaten or occupy every space on chessboards of varying sizes. After determining the patterns evident in this problem, we will attempt to find and prove formulas to describe those patterns.

Alex Cartagena and Mark Flora
Blue Ridge School

Tournament Score Sequences
Supervised by Jerry Jared, DCI 2001

We attempted to find a formula for the number of distinct score sequences for a tournament with n vertices. While we were unable to find an answer for n, we did get answers for n less than or equal to fifteen.

Alex Cartagena, Andrew Cocke, and YiHsuan Lee
Blue Ridge School

Solving the 24 Game
Supervised by Jerry Jared, DCI 2001

In the 24 Game, the objective is to use each of four given numbers exactly once and the operations of addition, subtraction, multiplication, or division to make the number 24. We developed a series of programs for the TI 83 Calculator that interact with each other and generate by brute force all possible solutions. We show how many calculations are required and explain how by symmetry some solutions appear more than once.

Amanda Denemark and Christie Williams
The Charter School of Wilmington

The Human Factor in the Art Gallery Problem
Supervised by Chuck Biehl, DCI Lead Teacher

The traditional art gallery problem asks for the minimum number of guards or cameras placed on the vertices of a polygon to "see" the entire interior. Our research started with this question for simple, not-necessarily convex n-gons, such that the entire interior is under simultaneous surveillance, but since this is a fairly traditional problem from computational geometry, we embodied the "human factor" by further stipulating that any vertex with a reflex angle in the polygon (i.e. >180 degrees in the interior) with a guard would actually require two. We felt this was a reasonable constraint given the limitation of human peripheral vision. By introducing the second guard at some vertices, the problem is no longer a matter of the smallest set of vertices with guards, but the set which minimizes the total number of guards.

Gustavo Garcia
Hillcrest High School

Applications of Domination in Graph Theory
Supervised by Sharon Edelkind, DCI 2000

I will be discussing the domination number of a graph, which is he smallest set of vertices such that every vertex is in this set of vertices or adjacent to it. My research involved basically two applications of domination. I used the idea of domination to determine the minimum number of security guards needed to cover each classroom on one floor of Hillcrest High School. I also worked on domination in regard to the placement of queens and other pieces on a chessboard.

Rebecca Gordon and Sarah Lyons
Port Allegany High School

Dominating the World
Supervised by Brian VanGorden, DCI 2000

The concept of differentiating sets lead to an exploration in world domination. Two unique variations on the domination theme, alternating, and length 2, will be presented as well as an application to world domination.

Lea Impagliazzo, Kendra Schmidt, David Beyel, Nick Canderan, and Ryan Scully
Upper Township Middle School

Guarding 3-D Orthogonal Polyhedra with Vertex Guards
Supervised by Dee Endicott, DCI 2001

What we are studying is a subset of the art gallery problems. In an art gallery problem we are trying to find the number of guards that are always sufficient and sometimes necessary to protect the inside of a 3 dimensional, orthogonal polyhedron. We have been able to find the number of guards if we have convex shapes or shapes with tunnels that are only come in from two different sides. We are will leave for future consideration polyhedra with indentations from three different sides.

Kari Kibler, Todd Lapa, Lillian Marino, Katie Melech, Adam Sarma,
Vonessa Toczynski, and Amy Zinner

Greece Arcadia High School

Chromatic Number of a Graph Using Vertex and Edge Coloring
Supervised by Carol Oehlbeck, DCI 2001

In this project, we explored vertex and edge coloring. Bipartite, complete, and n-regular graphs were used, as well as, paths, wheels, and cycles. Our discussion will define the steps associated with vertex and edge coloring and present practical applications of the topic.

Eric Leja and Craig Reynolds
Ponaganset High School

Domination of an n by n Chessboard
Supervised by David Brouillard, DCI 2001

The moves of a chess piece on an n by n square chessboard can be represented by a graph where each square is represented by a vertex and two vertices are adjacent if a piece can move from one square to the other. The problem of the minimum number of rooks and kings needed to dominate a chessboard was analyzed and solved. In addition, the problem of the queen's domination was analyzed for certain small values of n.

Ryan Meltzer and Drew Headley
Baruch College Campus High School

Color-graph Theory Project
Supervised by Gisele Nassif, DCI 2001

To apply color-graph theory and the four color theorem in three-dimensions. We will take the rules and tools developed in two-dimensions and apply them to three. There will also be an exploration of why the four color theorem exists in two-dimensions, and how three-dimensions allows for some of the limits of two-dimensions to go away. We have decided to impose more rules on our study in order to reduce the level of complexity that we are dealing with. There will be only similar shapes used, all the shapes will be three-dimensional, touching will constitute meeting between two sides, overlap is possible as long as a least one of the coordinates are different, all sides have definite edges.

Andrew Silverman
White Plains High School

Factoring Degree Sequences
Presentation supervised by Lisa (Gravitz) Weber, DCI 2000
Research supervised by Marty Lewinter, Purchase College

The research sought to find a sufficient condition for which a graphical degree sequence, S, is factorable. S is considered factorable if there exist graphs G and H where S is the degree sequence of G x H. S is considered (r,s)-factorable if the product of the orders of G and H, r and s, respectively, equals the order of S. Therefore, S is (r,s)-factorable if and only if there exists an r by s tableau where the boundary column (leftmost column) and the boundary row (topmost row) contain the sequences of G and H. The entries found within the tableau using the addition algorithm will be those of S. Furthermore, S is considered (r,s)-factorable only if the sum of its entries is less than or equal to rs(r + s - 2). This is because the sum of the entries of the degree sequence of the complete graphs of r and s is rs(r + s - 2), and the complete graphs provide the most possible adjacencies. Furthermore, a graphical sequence of length n is factorable only if the sum of its entries is less than or equal to n(n/2 rounded down). This is because the degree sum of a graph of order n is at most n(n - 1), and a factorable sequence can have at most 1/2 the degree sum of a complete graph. The research is a foundation for further studies in determining conditions for which a degree sequence is factorable. An all-inclusive condition is desired.

Davis Walker, Reggie Standish, and Carl Cohen
Greensboro Day School

Winning Strategies in Nim ? When Can You Win?
Supervised by Ron Varnum, DCI 2001

The paper analyzes versions of three-pile Nim, a popular two-player game, to determine which player has the winning strategy and what that strategy is. An analysis of two-pile Nim is given to aid in assessing variations of three-pile Nim. Using game trees, the group has sought to find a pattern in the combinations of three piles that will enable each player to possess the winning strategy. Open questions are given for an analysis of four-pile Nim.

Andrea Wilson
Port Allegany High School

Rumors in the Senior Class
Supervised by Brian VanGorden, DCI 2000

A senior class connectedness graph, based on mutual friendships, was constructed by the Discrete class . Connectedness will be discussed as well as dominating sets with a focus on distance 2 domination. An application to rumor spreading will also be presented.

Updated April 22, 2002