Jump to ContentJump to Main Navigation
Algorithmic Puzzles$
Users without a subscription are not able to see the full content.

Anany Levitin and Maria Levitin

Print publication date: 2011

Print ISBN-13: 9780199740444

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780199740444.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 04 March 2021



3 Hints
Algorithmic Puzzles

Anany Levitin

Maria Levitin

Oxford University Press

1. A Wolf, a Goat, and a Cabbage With one insignificant exception, the puzzle can be solved by making a sequence of the only moves available in each situation. 2. Glove Selection Imagine a malevolent adversary who wants you to draw as many gloves as possible before getting what you need. Note that gloves are not socks: they can be right-handed and left-handed. 3. Rectangle Dissection Triangles in question need not be of the same size. 4. Ferrying Soldiers Solve the problem of ferrying one soldier first. 5. Row and Column Exchanges The answer is “no”; determine why. 6. Predicting a Finger Count Reenact the girl’s count long enough to see a pattern that makes the answer obvious. 7. Bridge Crossing at Night The answer is “yes,” and the solution does not involve any tricks. 8. Jigsaw Puzzle Assembly A similar problem is discussed in the book’s tutorial on algorithm analysis techniques. 9. Mental Arithmetic There are at least two different ways to compute this sum. Both use the methods discussed in the tutorial on algorithm analysis techniques. 10. A Fake Among Eight Coins “Three” is not the correct answer to the puzzle. 11. A Stack of Fake Coins The answer is “one.” Take advantage of the fact that the scale gives the exact weight. 12. Questionable Tiling The answer is “no.” 13. Blocked Paths Use dynamic programming as explained in the tutorial on algorithm design strategies. 14. Chessboard Reassembly What parts of the board do you have to cut to solve the puzzle? 15. Tromino Tilings Only one of the three questions has a “yes” answer. 16. Making Pancakes What is the fastest way to make three pancakes? Also note that n = 1 is, in fact, a special case here. 17. A King’s Reach The puzzle statement does not forbid the king to visit the same square more than once. Also, make sure that your answer is correct for every value of n ≥ 1. 18. A Corner-to-Corner Journey Observe the colors of the squares the knight jumps through.

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .