
Store








CTK Exchange
Jess
guest

May1103, 12:56 PM (EST) 

"Bulgarian Goats Problem"

Hi, I have to admit I am new to this forum, but it looks very good! I'm a 14 year old maths freak, so I often look up previous past maths competitions, papers etc, and analyze them. However I am stuck on this particular question. I was wondering if someone could give me guidelines on ways to solve it, and what sort of catergory this sort of problem falls under? It is quite unique. Yenko the Bulgarian goatherd drives his father’s goats into a valley each morning and lets them browse there all day before driving them home in the evening. He notices that each morning the goats immediately separate into groups and begin to feed. The number and sizes of the initial groups vary. Some days there are nine or more groups; on other days, there are three or fewer. There can be groups of one or the whole herd can form a single group. About every five minutes one goat breaks away from each feeding group and these breakaway goats form into a new group. Yenko has noticed that by the afternoon, even though the goats continue their regrouping, the sizes of the groups have stabilized, and there are always seven feeding groups. a.) How many goats are there in the herd? What are the sizes of the feeding groups once they have stabilized? Yenko’s father then sells two of the goats. Over the next week, Yenko notices that things have changed. The sizes of the feeding groups no longer stabilize. There are not always seven groups. Nevertheless, a cyclic pattern of sizes develops every day. b.) Find at least two possible cyclic patterns of sizes.


Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


RicBrad
Member since Nov1601

May1203, 07:38 PM (EST) 

1. "RE: Bulgarian Goats Problem"
In response to message #0

Wow  this is a cool problem! If you just want a starting point, then think about the fact that the state is unchanged by the "new group forming" process. If you want an answer, read on: >Yenko the Bulgarian goatherd.... .... >...... one goat breaks away from each >feeding group and these breakaway goats form into a new >group. >........ the sizes of the groups >have stabilized, and there are always seven feeding groups. > >a.) How many goats are there in the herd? > What are the sizes of the feeding groups once they have >stabilized? Ok  at each step, every group loses one member, and these all form a new group. Because we have an equilibrium at the end of the day, there must be a group of only one goat, so one group ends as a new one is formed. By extension, there must be a group of 2, so that the singleton group is replaced at each step, and so on: Hence, in equilibrium, the groups are: {1,2,3,4,5,6,7} = 28 goats. > >Yenko’s father then sells two of the goats. >.... The sizes of the feeding groups no longer stabilize. >.... a cyclic pattern of sizes develops > >b.) Find at least two possible cyclic patterns of sizes.
Right: we have 26 goats now. How can we find cyclic patterns? This is a much harder problem  I can't see any obvious symmetry of the problem. I had to resort to using a computer  the number of groups stabilises pretty quickly at 6 or 7, I found these two cycles, but I'd like to see a more 'mathematical' way to find some. {6, 5, 5, 4, 3, 2, 1} {7, 5, 4, 4, 3, 2, 1} {7, 6, 4, 3, 3, 2, 1} {7, 6, 5, 3, 2, 2, 1} {7, 6, 5, 4, 2, 1, 1} {7, 6, 5, 4, 3, 1} {6, 6, 5, 4, 3, 2} {6, 5, 5, 4, 3, 2, 1} {6, 6, 5, 4, 2, 2, 1} {7, 5, 5, 4, 3, 1, 1} {7, 6, 4, 4, 3, 2} {6, 6, 5, 3, 3, 2, 1} {7, 5, 5, 4, 2, 2, 1} {7, 6, 4, 4, 3, 1, 1} {7, 6, 5, 3, 3, 2} {6, 6, 5, 4, 2, 2, 1}
I suppose these two are the most basic cyclic groups, as they have 1 and 2 pairs of groups of the same size, respectively. I don't know to what extent they are unique.
Thanks for this interesting problem, Rich 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 



alexb
Charter Member
972 posts 
May1303, 12:06 PM (EST) 

5. "RE: Bulgarian Goats Problem"
In response to message #1

There seems to be at least one other: {6, 6, 4, 4, 3, 2, 1} {7, 5, 5, 3, 3, 2, 1} {7, 6, 4, 4, 2, 2, 1} {7, 6, 5, 3, 3, 1, 1} {7, 6, 5, 4, 2, 2} {6, 6, 5, 4, 3, 1, 1} {7, 5, 5, 4, 3, 2} {6, 6, 4, 4, 3, 2, 1} 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 




Graham C
Member since Feb503

May1903, 09:29 AM (EST) 

8. "RE: Bulgarian Goats Problem"
In response to message #1

>I'd like to see a more 'mathematical' way to find some. >This seems to work, but it's still a conjecture. It always finds cyclic patterns but I can't be sure it finds them all. It finds all the solutions so far given for 26 goats. For an arbitrary herd of n goats: If n is triangular then the problem has already been solved. If n is NOT triangular the following algorithm seems to work. Write A for the number of goats in group i. Define the function k(x) as I defined it in another post  i.e. k(x) is the lowest integer k for which k(k plus 1)/2 >= x. Then A<0> = k(n) OR k(n)1 A = k(n  sum A, 0<j<i) OR k(n  sum A, 0<j<i)  1 (If you leave out the OR clauses this works for triangular n too, but with them in it generates spurious results.) In computing results, the OR clauses mean you have to build a binary tree, which means it gets complicated, but I've tested it out considerably. I'm not sure however that with large numbers you might have to consider, e.g., k(n) OR k(n)1 OR k(n)2. My earlier result that the length of the cycle is always k(n) remains true, with the caveat that you have to be prepared to treate a fixed point as an arbitrarily long cycle, and 'abab' as a cycle of 4. Strictly I suppose the length is always a factor of k(n). I'd attach my program that runs the algorithm, but it's too big. I could post the source if anyone's interested: it's written in Delphi.


Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 







Graham C
Member since Feb503

May1303, 08:20 AM (EST) 

2. "RE: Bulgarian Goats Problem"
In response to message #0

I also found this an interesting problem. For (a) my answer is the same as RicBrad's. However for (b) it may be interesting to note that you get one answer if you simply drop the group containing 2 goats from the answer to (a)  i.e. the groups are {1,3,4,5,6,7}  which actually is the same cycle as RicBrad's first example, though starting at a different point. It's also the grouping you get if you start with one group of 26 after 19 moves, i.e. {26}  {25,1}  {24,2}  {23,2,1}..... All of the previous 18 groupings obviously lead to the same cycle, so in looking for a different pattern you can ignore them as starting points, as you can ignore those in the cycle itself. There must surely be an analytic answer, but I can't see it either. Thanks again. which cycles as follows: 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 




alexb
Charter Member
972 posts 
May1303, 11:34 AM (EST) 

3. "RE: Bulgarian Goats Problem"
In response to message #0

This is really a nice problem. Where did it come from? Do you have a reference? Perhaps some insight may be gain if you run iterations for small numbers: 2 > (1, 1) > 2 3 > (2, 1) > (1, 2), (1, 1, 1) > 3 A simple general statement: for a triangular number M = N(N+1)/2, (1, 2, 3, ..., N) is a fixed point.


Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


Graham C
Member since Feb503

May1603, 08:59 AM (EST) 

6. "RE: Bulgarian Goats Problem"
In response to message #0

I have some progress to report on the generalised question. I started by looking at the case where the goats are initially in one group, and I define cycle in such a way that it includes, e.g. a,a,a as a cycle of three. Write n for the number of goats. The subsequent development can be shown in the following triangular table: {n} {n1,1} {n2,2} {n3,1,2} {n4,1,3} {n5,2,3} {n6,1,2,3} {n7,1,2,4} {n8,1,3,4} {n9,2,3,4} {n10,1,2,3,4} {n11,1,2,3,5} {n12,1,2,4,5} {n13,1,3,4,5} {n14,2,3,4,5} .... First define the useful function k(n) which equals the minimum value k where k(k+1)/2 >= n: i.e. it is the 'root' of the next triangular number greater than n, unless n itself is triangular, when it equals the 'root' of n. As examples, k(9)=4, k(10)=4 and k(11)=5. Note several things (writing x for the number of moves): a) the number of groups and the numbers in them (apart from the first one) are independent of n. b) each row has the same number of groups in each entry. c) when x is a triangular number, it'starts a new row. d) the number of groups in that row is k(x). Then When x=n, if x is a triangular number, then it is the first entry in its row, and it has the same number of groups, distributed in the same way, as the entry immediately above. That entry therefore starts a cycle (in this case it is also a fixed point). The cycle is k(n) moves long. If x is not a triangular number then the corresponding entry is the same as the entry above and to the left, which therefore also starts a cycle at nk(n), which is also k(n) long. One can therefore safely say that starting with {n} there is a cycle that starts after nk(n) moves and is k(n) long. (If n is triangular, then all entries in the cycle will be the same.) Now assume the goats start in one of the other distributions in the table (e.g. {n3,1,2} ). Obviously it eventually reaches the same cycle, which will still start at nk(n) and be k(n) long. Unfortunately, not all possible starting situations are included in the table. I'm still working on this but initially it appears that the cycles are still k(n) long, where n is now simply taken to be the total number of goats. I haven't yet figured out where the cycle begins in all these cases however. 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 



Graham C
Member since Feb503

May1603, 12:04 PM (EST) 

7. "RE: Bulgarian Goats Problem"
In response to message #6

Addendum I should perhaps have mentioned that I also count a cycle of, e.g., abab as a cycle of 4, as well as 2 cycles of 2. It occurs to me there is a simple proof that a cycle always exists. The number of possible ways of expressing a given integer as a sum of integers is finite. You have the possibility of an infinite number of moves. Ultimately, if no cycle occurs in the meantime, you must therefore get back to the starting arrangement. So the whole series to that point would be a cycle. 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 



Anthea
guest

May2003, 09:21 AM (EST) 

11. "RE: Bulgarian Goats Problem"
In response to message #0

Dear Jess, I sincerely hope you are not enrolled in the Mathematics Challenge for Young Australians since this problem (Bulgarian Goats) is a CURRENT problem for 2003 being run in Term 2. However, you probably are and now have some lovely answers that you can submit and get full marks for. I wonder if you have learnt anything? 

Alert  IP 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny
66167155

