There are 60 records given to you which correspond to a prisoner who is imprisoned for 60
days. He has 6 relatives one of whom visits him daily and the others visit him every i
th day from the day of his imprisonment (i=2,3,4,5,6 for these 5 relatives).
Every record is sealed with the day number on it which indicates the number of days he is jailed when the record is filed with the names of visitors on that particular day. You have to make a new record which should be filled with the following details:
visitor name - number of visits after 60 days
Assume that no other relatives visited him at all, names of these 6 relatives are different and you don't know their names. Find the minimum number of records that need to be checked to make the new record correctly. Find the number of ways you can choose the minimum number of records and you can still make the new record correctly.
3 is the minimum number of records.
First, let's consider it from an information theory point of view, without assuming that the relatives display any regularity.
Two days is not enough, because any given person is either there or not there on each of the two days, giving rise to 2X2 combinations = 4 combinations. Just not enough information, especially since somebody needs to be there in order for us to have their name. By looking at just two days, the best we can determine is divide all names into three (2 X 2 - 1) groups:
a) those there on both days
b) those there on just the first day
c) those there on just the 2nd day.
Three days is enough, in theory, to divide people into (2X2X2 - 1) = 7 groups. And there in, are in fact, many ways to do this with 3 days and 6 predictable relatives. For instance, pick days 6, 8, and 15.
Relative 1 is the one there on days 6, 8, and 15.
Relative 2 is the one there only on days 6 and 8.
Relative 3 is the one there only on days 6 and 15.
Relative 4 is the one there only on days 8.
Relative 5 is the one there only on day 15.
Relative 6 is the one there only on day 6.
While I could theoretically distinguish between 7 relatives, I didn't manage it with Relative 7 who comes on every 7th day. The problem is that there is too much overlap among the schedules of relatives 2,3,4, and 6. Whenever 6 is there, so is 2 and 3. Whenever 4 is there, so it 2.
And I haven't worked out how many different sets of 3 days we could look at the distinguish between 6 relatives, but there are several such sets. For instance, instead of looking at day 15, I could have used day 45, both of which have only relatives 1, 3 and 5 there. Instead of using day 6, I could have used 18 or 42 or 54, all of which have only relatives 1 and 2 and 3 and 6. Instead of using day 8, I could have used 16 or 32 or 42, all of which have only relatives 1 and 2 and 4. So, at a minimum, there are 2*4*4= 32 sets that would work.
Edited on January 21, 2009, 9:20 pm
Edited on January 21, 2009, 9:44 pm
better idea (spoiler, part I)
