High School Student Research Conference Abstracts 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.
Darly Kranec, Teresa Kwiatek, Rocco Loreti, Michael Nappa, Brianna Paolicelli, Michael Wallendjack Delaware Valley High School Variations of Tictactoe, who controls? Supervised by Richard Giantisco, DCI 2001 The outcome of every 2player game is controlled by one of the two
players. We have examined some variations of a popular 2player 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.
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.
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.
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.
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,
notnecessarily convex ngons, 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.
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.
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.
Upper Township Middle School Guarding 3D 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.
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 nregular 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.
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.
Baruch College Campus High School Colorgraph Theory Project Supervised by Gisele Nassif, DCI 2001 To apply colorgraph theory and the four color theorem in
threedimensions. We will take the rules and tools developed in
twodimensions and apply them to three. There will also be an
exploration of why the four color theorem exists in twodimensions,
and how threedimensions allows for some of the limits of
twodimensions 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 threedimensional, 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.
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
allinclusive condition is desired.
Greensboro Day School Winning Strategies in Nim ? When Can You Win? Supervised by Ron Varnum, DCI 2001 The paper analyzes versions of threepile Nim, a popular twoplayer game,
to determine which player has the winning strategy and what that strategy is.
An analysis of twopile Nim is given to aid in assessing variations of
threepile 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 fourpile Nim.
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.
