The Reve's Puzzle

Overview

This puzzle was first mentioned in Dudeney’s book “Puzzles of Canterbury” in 1907. Since then an optimal algorithm in the general case has not been obtained despite many attempts from people all over the world and the efforts of Dudeney himself. There are only partial results. That is why this attracted me and became my subject of investigation. Its principal objective is to find the minimal number of moves necessary to transport a stack of cheeses, in which smaller cheeses are placed on top of bigger ones, from the first stool onto the last following the rule: do not ever place any bigger cheese over a smaller one. We explored a few cases of this puzzle: 1) 3 stools, which is also called “The tower of Hanoi” 2) 4 stools 3) General case We formulated and proved the following results: Theorem 1. Let T_n=n(n+1)/2 be a triangular number and m\in{0,...,n-1}. The movement of T_n+m cheeses, using four stools, requires the minimal number of 1+(n-1)2^n+m2^n moves, for any natural n. Theorem 2. Let T_n^p is a simplex number. The movement of T_n^p+m (m=0,...,T_n^{p-1}-1) cheeses, using p stools requires no more than S_n^p+m2^n moves, where S_n^p=2^nT_n^p-2S_{n-1}^{p-1}-S_{n-1}^{p-2}-...-2S_{n-1}^2-S_n^1, where S_n^1=2^n-1. Conjecture 1. The number of moves given in Theorem 2 is minimal possible. This study showed that the Reve’s puzzle can be completed with no more than S_n^p+m2^n moves, where S_n^p=2^nT_n^p-2S_{n-1}^{p-1}-S_{n-1}^{p-2}-...-2S_{n-1}^2-S_n^1

Competition history

• ISEF 2017 Mathematics · Entry MATH039 Affiliated fair in Russian Federation

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.