OLYMPIADS IN INFORMATICS, 2016, Vol. 10, pp. 231 - 235
© IOI, Vilnius University

ISSN 1822-7732

DOI: 10.15388/ioi.2016.15

Problem Solving, Presenting, and Programming: A Matter of Giving and Taking

Tom VERHOEFF

Dept. of Math. and CS, Eindhoven University of Technology Eindhoven, The Netherlands
e-mail: t.verhoeff@tue.nl

Abstract

Nim is a well-known two-person game, where players alternate taking items from one of multiple piles. Finding a winning strategy for such games is a nice exercise in problem solving. Typically, the winning strategy for classical nim is explained in terms of nim sums, involving binary notation of numbers. I explain how to understand and play a winning strategy without prior knowledge of binary notation, which is useful when presenting this strategy in primary school. Programming that strategy is also an interesting challenge. This can be done elegantly in a functional language that supports patterns, such as the Wolfram Language. I conclude by giving you a variant of nim to work out yourself.

Keywords:

impartial games, nim, functional programming.


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


Copyright © International Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2016