Question 1202348: The prairie dogs were having a town meeting to talk about the blackfooted ferret that was terrorizing the neighborhood. One town council dog suggested building a network of tunnels connecting every burrow to every other burrow. Then someone said Are you crazy ? We have nine burrows. Thats too many tunnels nd too much money to build them. If each tunnel cost $1.00 to build, how much would it cost the prairie dogs to connect every burrow with every other burrow?
Found 2 solutions by ikleyn, math_tutor2020:
Answer by ikleyn(52790)   (Show Source):
Answer by math_tutor2020(3817)  (Show Source):
You can put this solution on YOUR website!
Answer: 36 tunnels
Total cost = $36
====================================================================
Explanation:
Let's say for example there are 5 burrows labeled A,B,C,D,E.
Make a 5 by 5 table with those labels along the left and top side.
It's clear it makes no sense to build a tunnel connecting any given burrow to itself. We cannot connect A to A for instance.
Let's cross those entries out with an X.
The 5*5 = 25 entries has now dropped to 25-5 = 20 entries. We've subtracted off the 5 cells marked with X.
In other words:
25 - 5
5*5 - 5*1
5*(5-1)
5*4
Meaning that if we had n burrows, then we'd have n^2 - n = n*(n-1) entries after removing the northwest diagonal.
But notice the symmetry of the table. The entries marked with Y represent connecting burrow A to C
We've double-counted things when marking two instances of Y.
So we ignore either the lower half or the upper half. The string of X's is the divider line.
This means we'll divide by 2 when ignoring half of the cells of the table.
There are 5*4/2 = 20/2 = 10 different tunnels connecting the five burrows together.
The ten tunnels are:
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
A tunnel like AB is the same as BA. Order doesn't matter.
The formula in general is n*(n-1)/2 which is found in the nCr formula when r = 2.
If we had n = 9 burrows, then,
n*(n-1)/2
9*(9-1)/2
9*8/2
72/2
36
There are 36 tunnels connecting the 9 burrows to each other. Each tunnel costs $1.00, which means the total cost is $36.
|
|
|
