- Problem #123 - Posted Monday, July 23, 2001
- Tour de Ants ! (back to top)
- Here are n ants who encounter
some 'forks in the road.' A
positive (whole) number
- of ants crawl along each
path. RULES: (1) The net ant flow around a loop is zero,
- (2) The same number of ants
go into a node as out.
a) Find the smallest number,
n,
- of ants that can do this.
b) What nine values {a,
b, . . . , i} will 'go with this flow'?
- Solution: Set up linear equations according
to the above rules. Here's Guha's solution:
- The equations satisfying the given
conditions are: (Dan's note:
6 nodes, 4 loops)
1) a+b=n . . . . 2) c+g=a .
. . . 3) e +d=b . . . . 4) c+d=h+f .
. . . 5) g+h+i=n
6) e+f=i . . . . 7) a+c-d-b=0 . . . . 8)
g-h-c=0 . . . . 9) h-i-f=0 . . . . 10)
d+f-e=0
from 4),6),9), we get f=(c+d+e)/3,i=(2e+c+d)/3,h=(2c+2d+e)/3
.... substituting f in (10),
- 4d+c-4e=0......(11)......from (3) and (11), 8d +c-4b=0.....(12)
now, g=n-h-i =n-(c+d+e)...
- [putting the values of h & i] also, g-h-c=0 so, n-(c+d+e)-(2c+2d+e)/3-c=0
so.....
- 3n-(d+4b+8c)=0..........(13) from (1)&(7), n-2b+c-d=0....(14)
.... solving (12),(13),(14),
- we get 33d=7n....The lowest integral value of n so that d is integral is 33 when
d=7
which gives c=4, b=15, a=18,
e=8, g=14, h=10, f=1, i=9.
- Dan's Note: Ok,
this is the coolest thing: The flow diagram exactly corresponds
to a tiling of a rectangle 33(=n)
by 32(=a+g) with nine squares of sizes a, b, c, ..., i !!
- See problem #32 - Squares
in a Box
|
 |