Arnold's Challenges

Here are five challenges that build on the ideas you’ve been working with. You might like to do one a day... The first one of each set should be fairly easy, but they get harder. What do you get out of this? Just the warm feeling you get when you know you've solved one of Arnold's challenges, and the satisfaction of knowing that you've mastered a deep idea from computer science.

Enjoy the challenges!

Design your own decision tree for guessing numbers between 0 and 15, and test it with a friend.

Design a decision tree for guessing numbers between 0 and 31. How many questions do you need to ask to guess one of these numbers?

Correct! Great work!

Sorry, that is incorrect.

Please enter an answer.

Think about a decision tree for guessing numbers from 0 to 255 (don’t draw it, as it will be very large!) If each question always divides the range in half, how many questions does it need to ask?

Correct! Great work!

Sorry, that is incorrect.

Please enter an answer.

Suppose you made a tree for guessing numbers from 0 to 511. If each question always divides the range in half, how many questions does it need to ask?

Correct! Great work!

Sorry, that is incorrect.

Please enter an answer.

Design a decision tree for guessing numbers from 0 to 7, but make the question at the top "x ≥ 2". Does this make some numbers quicker to guess, and others harder?