Domino Crime

Computer Science Level 1

You are a detective investigating a crime scene. On the floor lie dominoes--someone arranged them and induced a toppling chain-reaction. The policemen are about to collect the dominoes to identify the suspect's fingerprints. Your sidekick, Dr. Watson, claims,

"We don't have to check all the dominoes. First pick a random domino, and keep looking back at the domino it falls under until one that has no domino topples on. The suspect must have manually pushed that, which then will contain his/her fingerprint."

Here are three configurations of dominoes found at the crime scene. The nodes represent dominoes, and the arrows from u u to v v indicate domino u u toppled on domino v v .

Which of these fails Watson's method?

O-shaped configuration Y-shaped configuration U-shaped configuration

Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Geoff Pilling
Feb 11, 2017

For the O-shape configuration \boxed{\text{O-shape configuration}} all the dominoes will have fallen down, so there is no way to tell which was pushed.

3 Helpful 0 Interesting 0 Brilliant 0 Confused

I would like to add some additional points.

For the Y-shape configuration, the tricky part is the middle domino with two dominos fallen on it. In this case, we could still find the domino with suspect's fingerprint no matter which one we backtracked on. All of them have fallen, so both sources must be pushed manually. Hence both path leads to a domino that contains the suspect's fingerprint.

Anyway, Watson's method isn't perfect. What is the ideal way to deal with this problem?

Christopher Boo - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...