five kilometers, thus one more kilometer than
the first player.
Question 1. By playing differently,
beginning with the first move, could
the first player acquire the rights to
more of the line segment than the
Solution to question 1. Yes. If the
first player takes kilometers 2 to 3,
then the second player could take
kilometers 0 to 2, but then the first
player would take kilometers 3 to 5.
The first player would thus get three
of the five kilometers.
Question 2. Is there a minimal
amount by which one player can win
regardless of the length L of the segment?
Answer. Yes. The first player can
win by at least one kilometer every
time by going in the middle, meaning
the halfway point of the first player’s
kilometer is at position L/2. After
that, the first player would mirror the
second player’s moves. So if the second player takes x to x+ 2 to the left of
[CONTINUED FROM P. 144]
ARL Distinguished Postdoctoral Fellowships
The Army Research Laboratory (ARL) Distinguished Postdoctoral Fellowships
provide opportunities to pursue independent research that supports the mission
of ARL. The Fellow benefits by having the opportunity to work alongside some of
the nation’s best scientists and engineers. ARL benefits by the expected transfer
of new science and technology that enhances the capabilities of the U.S. Army
and the warfighter in times of both peace and war.
ARL invites exceptional young researchers to participate in this excitement as ARL
Distinguished Postdoctoral Fellows. These Fellows must display extraordinary
abilities in scientific research and show clear promise of becoming outstanding
future leaders. Candidates are expected to have already successfully tackled
a major scientific or engineering problem during their thesis work or to have
provided a new approach or insight, evidenced by a recognized impact in their
field. ARL offers five named Fellowships honoring distinguished researchers
and work that has been performed at ARL. Three of these positions are open for
the 2019 competition.
The ARL Distinguished Postdoctoral Fellowships are one-year appointments,
renewable for up to three years based on performance. The annual stipend is
$100,000, and the award includes benefits and potential additional funding for
the chosen proposal. Applicants must have completed all requirements for a
Ph.D. or Sc.D. degree by the application deadline and may not be more than
five years beyond their doctoral degree as of the application deadline. For more
information and to apply, visit www.nas.edu/arl.
Online applications must be submitted by May 31, 2019 at 5 PM EST.
the middle kilometer, then the first
player takes (x + L/2) to (x + 2 + L/2) on
the right of the middle. The net effect
is the first player can always guarantee to capture at least as much territory as the second player on the two
sides of that middle kilometer. The
first player wins by at least the kilometer of the first move.
Upstart 1. Characterize situations
in which the first player can guarantee to win by more than one kilometer or prove it cannot be done.
Upstart 2. Suppose the line segment is of length L, but there are now
k players instead of two. The rules are
a direct generalization of the original
game; the first player may take one
kilometer, the second player two, the
third player three, ... the kth player k,
the first player then takes k+ 1 ... and
so on, all without overlap. Is there
some length L and some number of
players k whereby a player other than
the first player can guarantee to capture more of the line segment than
Upstart 3. Suppose the government
leased out vertical cross-sectional
squares belowground. Each player
would thus take squares, with the side
length of each square increasing by
one kilometer with each move. The
first player takes one kilometer
squared. The second player then gets
two kilometers squared. The first player then gets three kilometers squared,
and so on, again without overlap. Does
either player have a winning strategy if
the area available to lease could be an
arbitrary rectangular cross-section belowground? How would this generalize to more players?
All are invited to submit their solutions to
email@example.com; solutions to upstarts
and discussion will be posted at http://cs.nyu.edu/cs/
Dennis Shasha ( firstname.lastname@example.org) is a professor
of computer science in the Computer Science Department
of the Courant Institute at New York University, New
York, USA, as well as the chronicler of his good friend the
omniheurist Dr. Ecco.
Copyright held by author.
Advertise with ACM!
Reach the innovators and thought leaders
working at the cutting edge of
computing and information
technology through ACM’s magazines,
websites and newsletters.
+ 1 212-626-0686
Request a media kit
with specifications and pricing: