## mathmath333 one year ago Counting question

1. mathmath333

There are $$12$$ towns grouped into $$4$$-zones with $$3$$ towns per zone. It is intended to connect the towns with telephone lines such that every $$2$$ towns are connected with $$3$$ direct lines if they belong to the same zone, and with only $$1$$ direct line otherwise. How many direct telephone lines are required?

2. ParthKohli

Nothing much to think about here. Consider one zone. If we look at the lines within that zone, there are $$3\cdot \binom{3}{2}$$ lines since there are 3 lines per two towns. Thus, overall, there are $$3\cdot 3 \cdot \binom{3}{2}$$ lines that connect towns in the same zone. Now let's look at towns that don't belong to the same zone. For every town, there are six towns that do not belong to the same zone as that particular town, and thus, we find the number of towns and multiply that by 6 to find the lines that connect towns NOT belonging to the same zone.

3. ParthKohli

Not six towns - I meant nine.

4. mathmath333

well i m yet to study probablity, is there any alternate way

5. ParthKohli

Also that should be $$4\cdot 3 \cdot \binom{3}2$$

6. ParthKohli

|dw:1434886089734:dw|

7. ParthKohli

We can divide the lines into two sorts: - Lines connecting towns within the same zone. - Lines connecting towns in different zones.

8. mathmath333

i counted lines in same zone , -> 36

9. ParthKohli

Now let's focus on any one zone. How many lines are there in one zone? There are three lines connecting every two towns, and there are exactly three couples of towns (towns A, B; B, C and A, C). So there are 9 lines within one zone. And so the total lines are 36.

10. ParthKohli

Now to calculate the lines that connect two towns not in the same zone, let's look at any town. There are exactly 9 towns connected to any town that do not belong to the same zone as the town, right? So there are 9 such lines for every town. Meaning that the total lines of this kind = number of towns * 9 = 12 * 9 = 108.

11. mathmath333

9*12=108 (why u took 12)

12. ParthKohli

Because there are 12 towns, haha.

13. mathmath333

14. ParthKohli

Hmm, I don't see how. I'm sure we haven't double-counted anywhere.

15. ikram002p

|dw:1434887071634:dw|

16. ikram002p

like this ? |dw:1434887174189:dw|

17. ikram002p

|dw:1434887301011:dw|

18. mathmate

I would connect every town to each other by 1 line, which is the equivalent of a complete graph, giving 12*11/2=66 lines. Within each zone, to add the requirement of 3 lines between towns, we have to $$add$$ two lines between towns, which is 3*2 lines per zone, or 24 lines for 4 zones. That gives a total of 66+24=90 lines.

19. ikram002p

lol so it would be 9*4+9*7=99 hmm

20. ikram002p

i must have 9 extra lines

21. ikram002p

ok i think i should have another way ;) can u imagine this as 3 D ?? |dw:1434887567296:dw|

22. ikram002p

this is how geometry fellow do it :P |dw:1434887663717:dw|

23. ikram002p

each point out side define a town each point inside define 3 towns each z define a zone

24. ParthKohli

Not sure why it's confusing... it was clear that we had to divide by two to avoid double-counting.

25. ikram002p

now first imply the triple points |dw:1434887838678:dw|

26. ParthKohli

That double-counting thing was intended as a hint. The reason why it is not 108 but 54 is that if A connects B, then B connects A.

27. ParthKohli

So the answer turns out to be 36 + 54 = 90

28. ParthKohli

This question reminds me of graph theory.

29. ikram002p

|dw:1434888136335:dw|

30. ikram002p

|dw:1434888298736:dw|

31. ikram002p

|dw:1434888512346:dw|

32. ikram002p

now my final answer :D |dw:1434888621084:dw|

33. ikram002p

dont thank me, it was really long time since i did graph theory :P