This week's El País' math challenge (Spanish video) is again about a graph. In this case, the graph is a cube (8 vertex, 12 edges) numbered as shown in the video.
An ant starts walking from vertex #1 and changes it direction at random on each vertex (might even turn back from the same edge it came from). Vertex #7 and #8 are poisoned. If the ant happens to walk into one of them it will die. The challenge consist in find out the probabilities of the ant dying or not and in which vertex (#7 or #8) when it does.
This program uses the previous one (which already defines a Graph class) to make a simple statistical simulation of the problem and give you an answer of what to expect. Obviously, the result by itself is not the entire solution: you also have to give a theoretical demonstration of such result ;-)
#!/usr/bin/env python # -*- coding: utf-8 -*- # vim:ts=4:et:sw=4: from random import choice from grafo import Graph, Vertex class Point(Vertex): '''A vertex which can have a poison trap ''' def __init__(self, *args): Vertex.__init__(self, *args) self.poisoned = False def __str__(self): tmp = '*' if self.poisoned else '' return '< ' + tmp + str(self.i) + '>' class Cube(Graph): ''' A Graph derived class in which each vertex (Point) may contain a poison trap or not ''' def add(self, node, *nodelist): vertex = Point(node, *nodelist) self.vList[node] = vertex def run(self, N): """ Puts an ant on vertex #1 and let it run for N random steps. Stops when the ant enters a poisoned vertex or it has run N steps. Returns ant's last position. """ i = 0 pos = 1 # Initial ant position while i < N: i += 1 pos = choice(self.vList[pos].nodeList) if self.vList[pos].venenoso: break return pos if __name__ == '__main__': G = Cube() G.add(1, 2, 4, 5) G.add(2, 1, 3, 6) G.add(3, 2, 4, 7) G.add(4, 1, 3, 8) G.add(5, 1, 6, 8) G.add(6, 2, 5, 7) G.add(7, 3, 6, 8) G.add(8, 4, 5, 7) G.vList.poisoned = True G.vList.poisoned = True # Carry out simple statistics stats = [0, 0, 0] # Counters for i in xrange(1000000): # Total number of experiments (runs) pos = G.run(100) # make the ant to run 100 steps if pos > 6: # Map 0..6 => 0, 7 => 1, 8 => 2 pos -= 6 # 7 = 1, 8 = 2 else: pos = 0 stats[pos] += 1 # Increase corresponding counter tot = sum(stats) # Total #number of experiments (must be the same number as above) print stats # Absolute Frequencies print [100 * float(x) / tot for x in stats] # Relative frequencies (percentage)