Cullinan Shenanigans; Magic Camera

Computer Science Level 3

The Cullinan 1 Diamond (a.k.a.: The Great Star of Africa) has been stolen. In order to catch the culprit, world renown scientists Bill Nye and Neil deGrasse Tyson have engineered a camera that can take pictures of the past. Unfortunately, taking pictures of the past is very expensive. You have been hired to develop the optimal strategy for the right moments to take the pictures. When you take a picture, you can see one of three things: The diamond in the case, an empty case, or the culprit in the act. After a detailed investigation, evidence suggests that the culprit was a master thief, but it must have taken him more than $10$ minutes to steal the diamond. Evidence also suggests that he must have stolen it on Sunday, within a $24$ hour period.

What is the maximum number of pictures you need to take to catch the culprit if you use the best strategy?

Inspired by You Be the Detective .

The answer is 8.

1 solution

Brock Brown
Jul 29, 2015

Edit: This answer is wrong. I will update it soon.

If we know that the culprit must have stolen it somewhere between 00:00-24:00 , what's the best moment to take the first picture? We can cut the amount of search time in half by taking the picture at 12:00 ; this is because we will know if the diamond has already been stolen or not. If it hasn't already been stolen, then we know it will be stolen after 12:00 ; if it has been stolen, then we will look before 12:00 . We can apply this same technique over and over again to cut the search space in half. 24 hours = 1440 minutes needs to be divided by two $\boxed{8}$ times in order to eliminate the search space down to less than 10 minutes . This commonly used algorithm is known as the bisection method .

Python 3.3

search_minutes = 24*60
photos = 0
while search_minutes > 10:
    photos += 1
    search_minutes /= 2
print ("Pictures required:", photos)

I think you lack "mathematical rigor", how do you know that bisection method is the best answer?

Pi Han Goh - 5 years, 10 months ago

You actually have to reduce the interval to a 20 minute period. If you take a picture in the middle of that 20 minute period, you either catch the thief at the beginning of his job, or the end of his job, or somewhere in between.

So I think the correct answer is 7.

Steven Perkins - 5 years, 10 months ago

You know, I think you might be right, I'm not sure though... I'm at work right now, but I will post a report in the morning.

Edit: actually, I think it's still 8, but you definitely bring up an interesting point about being able to guarantee photographic evidence at 20 minutes or less. At 6 photos you can eliminate the search space to about 22.5 minutes; if you take another photo, you bring the search space down to 11.25 minutes, and one last photo will be guaranteed to catch the culprit (since 11.25 is less than 20 minutes), bringing the total to 8.

Brock Brown - 5 years, 10 months ago

Hmm. Interesting point.

Ok, factor in that at each photo you also eliminate 10 minutes from the search space. I initially thought it was 20 minutes eliminated, but I've convinced myself that it's 10. Then you certainly can get down to only 7 pictures if you do it optimally.

A deeper problem then it appears to be on the surface, right?

Steven Perkins - 5 years, 10 months ago

@Steven Perkins – You're actually right, it's 7, I have posted a report.

Brock Brown - 5 years, 10 months ago

@Brock Brown – I'm sure the answer is 8. By that logic, the answer for a 60-minute interval should be 2; show me one such strategy. (If that's too restrictive, solve 41-minute in 2 pictures.)

Ivan Koswara - 5 years, 10 months ago

@Ivan Koswara – ...Crap, you're right.

I was under the impression that you could eliminate all ten minute periods that intersect with the moment that you took the picture, but I realize now that doesn't make sense; you could have taken the picture right after he left or right before he did it. What we CAN do, however, is guarantee a picture of the thieves if we have our minutes down to 20 or less; this is because all ten minute regions would intersect in the middle.

Here's a gif describing a worst case scenario (three pictures) in a 60-minute interval:

Could you do me a favor and post a report? I can't post one because I've already posted one. I tried deleting it and trying it again, but it wouldn't let me.

Python 3.4:

search_minutes = 24 * 60
photos = 0
heist_time = 10
while search_minutes > heist_time * 2:
    photos += 1
    search_minutes /= 2
photos += 1 # take the last photo
print ("Pictures required:", photos)

Brock Brown - 5 years, 10 months ago

@Brock Brown – By the way, here are two things that you can consider:

You can consider the whole thing; the entire heist must lie in your search space. Thus it's enough to reduce the space down to 20 minutes or less, and one more picture finishes it. But snapping a picture in the middle only splits the search space in two, without reducing it further by 10 minutes.

Or, you can consider the start time only. The search space is reduced by 10 minutes (the last 10 minutes can't be the starting time), and whenever you snap a picture, you reduce the search space down by 10 minutes (those where starting on that time would intersect your picture), before halving it. But now you need to reduce your search space to 10 minutes or less.

The mistake is that you mix the two together: You use the reducing by 10 minutes, but your target is to get the search space to 20 minutes, not 10 minutes.

Ivan Koswara - 5 years, 10 months ago

Cullinan Shenanigans; Magic Camera

The answer is 8.

1 solution

0 pending reports