29th Annual Spring Programming Contest
The Math and Computer Science Department recently hosted its annual Spring Programming Contest which drew 16 teams from six colleges. Denison fielded five teams with 17 students. There were 57 students total. The contest consisted of six questions and each question was completed by some team. Top awards went to Oberlin – first and second place – with the team of Alivia Tacheny, Quang Nguyen,and Hieu Nguyen from Denison coming in a close third. Thanks to Dr. Ashwin Lall with the help of Tony Silveira for organizing this event.
How hard were the questions? Try your hand at the “Kevin Bacon” question below. It had the fewest correct solutions!
Problem E: Kevin Bacon
You’ve likely heard of the six degrees of Kevin Bacon. The conjecture is that almost all actors can be connected back to Kevin Bacon using six or fewer films. Two actors are connected if they have acted in the same film.
We will call a path from some actor to Kevin Bacon a minimal path if it uses the minimal number of films possible. Of course, there may be more than one minimal path. Some actors are connected more strongly; we will say actors A and B are strongly connected if for any minimal path connecting A and B and any film F on that path there is another minimal path connecting A and B that does not contain film F.
For this problem, you will determine how many actors are strongly connected to Kevin Bacon. For example, Kevin Bacon and Mark Wahlberg co-starred in Patriots Day and Mark Wahlberg co-starred in Deepwater Horizon with Kurt Russell, giving a minimal path of length two between Kevin Bacon and Kurt Russell. Kurt Russell is also strongly connected to Kevin Bacon since he was in Forest Gump (as the voice of Elvis) with Tom Hanks and Tom Hanks was in Apollo 13 with Kevin Bacon, making a second minimal length path between the actors. Since removing any single movie does not change the distance between Kevin Bacon and Kurt Russell, we can see that they are strongly connected.
Your task is to count the number of actors that are strongly connected to Kevin Bacon.