<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-186

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

U. Zwick and M.S. Paterson, The Memory Game (August 1, 1991).

Abstract

The memory game is a popular card game played by children and adults around the world. Good memory is one of the qualities required in order to succeed in it. This however is not enough.When it is assumed that the players have perfect memory, the memory game can be seen as a game of strategy. The game is analysed under this assumption and the optimal strategy is found. This is simple and perhaps unexpected. In contrast to the simplicity of the optimal strategy, the analysis leading to its optimality proof is rather involved. It supplies an interesting example of concrete mathematics of the sort used in the analysis of algorithms. It is doubtful whether this analysis could have been carried out without resort to experimentation and substantial use of automated symbolic computation.

<%@ include file="cited.html" %>

U. Zwick and M.S. Paterson, "The Memory Game", Theoretical Computer Science 110, pp. 169-196 (1993)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>