All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Prisoner's Visitors Problem (Posted on 2009-01-21)
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 ith 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.

 See The Solution Submitted by Praneeth Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 (all solutions) UNCURSED! | Comment 5 of 7 |
Daniel:

The number of sets is less than 666, a lot less.  While I might be wrong, I calculate it as 80.

You are still missing a few insights.  You are correct, for instance that 4 and 6 each must be in just one file.  However, they need to be in different files!  For instance, your first "solution" is days 2, 3, and 60, but this set doesn't work.  We can use it to identify relatives 1, 2 and 3, but it does not distinguish among relatives 4 or 5 or 6, because each of is them represented in the 60 day file only.

So here's my solution:

Lets say that the first file is the one with the 6.  It is a multiple of 2 and 3, so they are both in file 1.

And let's say that the 2nd file is the one with the 4.  It is a multiple of 2, so 2 is also in the 2nd file.

The third file cannot have 2, or otherwise we couldn't distinguish it from 1.  It must be in the 1st and 2nd files only.

Given that 3 is also in the 1st file, it must also be in the 3rd.  It cannot be in all 3 files (since it would look like 1), and it cannot be in just the 1st (since it would look like 6) and it cannot be in the first two (since it would look like 2). Hence, it is in 1st and 3rd.

And where is 5?  In order to be distinguishable from the others, it must be in just the 3rd file, or in the 2nd and 3rd files.

THEREFORE:
File 1 has 2, 3, 6, but not 4 or 5.   Possibilities are 6 * (1 or 3 or 7 or 9).  In other words, Day 6, 18, 42 or 54.  4 possibilities.

File 2 has 2, 4, not 3 or 6, and optionally 5.  Possibilities are 4 * (1 or 2 or 4 or 5 or 7 or 8 or 10 or 11 or 13 or 14).  10 possibilities.

File 3 has 3 and 5, but not 2 or 4 or 6.  Possibilities are 15 * (1 or 3).  In other words, 15 or 45.  Two possibilities.

TOTAL POSSIBILITIES = 4 * 10 * 2 = 80.  Four score, not sign of the beast.

Edited on February 26, 2009, 10:09 am
 Posted by Steve Herman on 2009-01-22 00:13:50

 Search: Search body:
Forums (2)