Jump to ContentJump to Main Navigation
Algoristhmic 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: 27 October 2021



(p.32) 2 Puzzles
Algoristhmic Puzzles

Anany Levitin

Maria Levitin

Oxford University Press

1. A Wolf, a Goat, and a Cabbage A man finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the man himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Show how the man can get all these “passengers” to the other side. 2. Glove Selection There are 20 gloves in a drawer: 5 pairs of black gloves, 3 pairs of brown, and 2 pairs of gray. You select the gloves in the dark and can check them only after a selection has been made. What is the smallest number of gloves you need to select to guarantee getting the following? (a) At least one matching pair (b) At least one matching pair of each color 3. Rectangle Dissection Find all values of n > 1 for which one can dissect a rectangle into n right triangles, and outline an algorithm for doing such a dissection. 4. Ferrying Soldiers A detachment of 25 soldiers must cross a wide and deep river with no bridge in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one soldier. How can the soldiers get across the river and leave the boys in joint possession of the boat? How many times does the boat pass from shore to shore in your algorithm? 5. Row and Column Exchanges Can one transform the left table in Figure 2.1 into the right table by exchanging its rows and columns? 6. Predicting a Finger Count A little girl counts from 1 to 1000 using the fingers of her left hand as follows. She starts by calling her thumb 1, the first finger 2, middle finger 3, ring finger 4, and little finger 5.

Keywords:   Bulgarian solitaire, Fibonacci numbers, Icosian Game, Josephus problem, Manhattan distance, card puzzles, decimal numbers, liquid pouring problems, monomino

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 .