[8 7. A canadian farmer has a field in which lives a herd of n tibetan yaks. The

Question

[8 7. A canadian farmer has a field in which lives a herd of n tibetan yaks. The farmer, having drunk too much raksi1 starts believing that the yaks are gossiping about him. He thus decides to partition the field by adding fences, so every yak will be in its own closed area (no two yaks will be together). The farmer inserts fences one at a time; no two of them can cross, although they may touch, and each fence separates an already enclosed part of the fields into two smaller pieces, both of which contain at least one yak (see the picture, in which the fences were added in the order green, light blue, magenta, light red and yellow) a traditional distilled alcoholic beverage in Nepal and Tibet Prove that no matter how the farmer inserts the fences, he will need to build exactly n - 1 fences (not including those that originally delimited the field)

Explanation / Answer

Solution:

Consider this problem as a graph where the fences are the edges and the yalks are vertices of the graph,

Now the problem is to put the fences in such a way that all the yalks are separated and cannot talk

So, this is turned out to be a connected graph problem in which we have to make sure that all the fences are connected in such a way that they are separating the yalks

So all we need to do is connect all the vertices which won't result in a cycle.

and we know the theorem which says to build a connected graph one need at least n-1 edges.

This means that n-1 fences will be enough.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.