1
$\begingroup$

Suppose that you have a book of 1000 pages.

You know the book has 10 chapters and know each chapters has at least 10 pages, i.e., as chapter 1 starts at page 1, chapter 2 can only start at the page 11 or after. When you are at a given page (and its next page), you are given its chapter's number, e.g. page 500 could be chapter 8 and page 501 would be either chapter 8 or first page of chapter 9.

What would be an optimal strategy to determine the pages of the 9 chapters, from chapter 2 to 10, by opening as few pages as possible in the book?

Please note that there is no table of contents in this puzzle-book :) Also, you don't know in advance if the book is designed in a certain way, for instance to defeat a solution or if it is a random book of 1000 pages and 10 chapters of at least 10 pages.

Puzzle improved thanks to @Bob Bixler and @Bass' comments.

$\endgroup$
6
  • $\begingroup$ The best algorithm would probably be a binary search. $\endgroup$ Commented Jul 4 at 10:50
  • $\begingroup$ So the aim is to find where each chapter starts. Is that right? And we already know where Chapter 1 starts. $\endgroup$ Commented Jul 4 at 10:57
  • $\begingroup$ @Lucenaposition, yes that is right :) $\endgroup$
    – JKHA
    Commented Jul 4 at 13:55
  • $\begingroup$ Optimal for average or worst-case behavior? $\endgroup$
    – Retudin
    Commented Jul 4 at 16:59
  • $\begingroup$ @Retudin, as you wish. It could be least max regret if you prefer :) $\endgroup$
    – JKHA
    Commented Jul 4 at 17:40

2 Answers 2

1
$\begingroup$

I think the best algorithm is simply a binary search for each chapter boundary.

There's a bit of improvement to be had by taking the 10 page minimum into account, such that the search begins with pages 11-991, and the 9 pages following a discovered chapter division are ignored in future divisions. Because of this, it's slightly better to look for the chapters in the denser regions first, as pointed out by Ross Millikan, since do so maximizes the chance that you find a chapter just on the boundary of another chapter's range, which will slightly shrink that range.

$\endgroup$
1
  • $\begingroup$ I think there is a tiny improvement in completing the search where chapters are dense first, so if you first check page 500 and find it is in chapter 7 you should next check 250 and complete the search in the first half before going on to the second. You have a higher chance of a chapter boundary in the last few pages, which will eliminate some pages from the search of the other half. $\endgroup$ Commented Jul 5 at 2:19
-3
$\begingroup$

Optimal strategy would be to get to the next chapter by turning the page forward if the current page's chapter before chapter 9. If the current page is in chapter 9 or 10, the turn pages anticlockwise to get to the 9th chapter. Once you get to the next chapter, you can calculate the page number for the 9 chapters because each chapter has only 10 pages.

For example: if the given page number is 100 with chapter 2, then we will move forward to get to the next chapter. After turning 2 pages we get to chapter 3 with page number 102. Then we can calculate the 9th chapter will be pages 162 to 171 (the 3rd starts from 102, then 6 chapters are 10*6 = 60 pages, so the 9th chapter starts at page 162)

$\endgroup$
2
  • $\begingroup$ Welcome to PSE (Puzzling Stack Exchange)! $\endgroup$ Commented Jul 4 at 17:53
  • 1
    $\begingroup$ The chapters are not only 10 pages. They have AT LEAST 10 pages each, but can have many more. There are 1000 pages, so on average they have 100 pages each. $\endgroup$ Commented Jul 4 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.