1

First question here on StackExchange! Sorry if this question is not quite of the correct style - please let me know if so.

Anyway, here's the context. I'm trying to write a program to determine a date of birth (not the year, just the day/month) in as few yes/no questions as possible. Now, the best I can do is a maximum of 13 questions for 31st of December, and 6 questions for 1st of January.

I'm not too great at maths, so I'd be alarmed if 13 is in fact the lowest maximum possible. Is there anyone out there who knows the answer (and if not, could explain how they tackle the problem of finding out)?

PS, sorry for the tags.. I have no idea what this question would be tagged as!

Cathal
  • 113

1 Answers1

4

Note that $256 \lt 366 \le 512$. You can distinguish between $512=2^9$ possibilities with nine questions.

Christopher King
  • 10,365
Mark Bennet
  • 100,194
  • Thanks! Could you explain where you got that inequality from? – Cathal Oct 22 '14 at 21:59
  • The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time). – hardmath Oct 22 '14 at 22:00
  • 1
    @Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc. – Mark Bennet Oct 22 '14 at 22:05
  • Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions! – Cathal Oct 23 '14 at 14:29
  • @Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway. – Mark Bennet Oct 23 '14 at 15:57
  • Thanks very much. Got it working. You've been quite helpful :) – Cathal Oct 23 '14 at 18:04
  • @Cathal - Thank you. It is a pleasure to give a little help to people like you. – Mark Bennet Oct 23 '14 at 21:18