CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Bulgarian Goats Problem"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange High school Topic #235
Reading Topic #235
Jess
guest
May-11-03, 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 Printer-friendly page | Edit | Reply | Reply With Quote | Top

  Subject     Author     Message Date     ID  
Bulgarian Goats Problem Jess May-11-03 TOP
  RE: Bulgarian Goats Problem RicBrad May-12-03 1
     RE: Bulgarian Goats Problem alexb May-13-03 5
     RE: Bulgarian Goats Problem Graham C May-19-03 8
     RE: Bulgarian Goats Problem Graham C May-19-03 9
         RE: Bulgarian Goats Problem Graham C May-19-03 10
  RE: Bulgarian Goats Problem Graham C May-13-03 2
     RE: Bulgarian Goats Problem alexb May-13-03 4
  RE: Bulgarian Goats Problem alexb May-13-03 3
  RE: Bulgarian Goats Problem Graham C May-16-03 6
     RE: Bulgarian Goats Problem Graham C May-16-03 7
  RE: Bulgarian Goats Problem Anthea May-20-03 11

Conferences | Forums | Topics | Previous Topic | Next Topic
RicBrad
Member since Nov-16-01
May-12-03, 07:38 PM (EST)
Click to EMail RicBrad Click to send private message to RicBrad Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
972 posts
May-13-03, 12:06 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
May-19-03, 09:29 AM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
May-19-03, 09:29 AM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
9. "RE: Bulgarian Goats Problem"
In response to message #1
 
   I'm sorry - I didn't preview my post. I used square brackets, and at one point included an i between them so everything went italic. The various appearances of A in the algorithm should be A(i), or A(0) or A(j) as appropriate (should be possible to interpret which goes where).


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
May-19-03, 02:51 PM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
10. "RE: Bulgarian Goats Problem"
In response to message #9
 
   Also I should have said the algorithm stops when A(x) = 0 (and you don't include the zero).


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
May-13-03, 08:20 AM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
972 posts
May-13-03, 11:36 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
4. "RE: Bulgarian Goats Problem"
In response to message #2
 
   >There must surely be an analytic answer, but I can't see it
>either.

I am not sure about that. It's easy to establish (by the pigeonhole) the existence of cycles, but not their exact composition.


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
972 posts
May-13-03, 11:34 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
May-16-03, 08:59 AM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
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}
{n-1,1} {n-2,2}
{n-3,1,2} {n-4,1,3} {n-5,2,3}
{n-6,1,2,3} {n-7,1,2,4} {n-8,1,3,4} {n-9,2,3,4}
{n-10,1,2,3,4} {n-11,1,2,3,5} {n-12,1,2,4,5} {n-13,1,3,4,5} {n-14,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 n-k(n), which is also k(n) long.

One can therefore safely say that starting with {n} there is a cycle that starts after n-k(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. {n-3,1,2} ).

Obviously it eventually reaches the same cycle, which will still start at n-k(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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
May-16-03, 12:04 PM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Edit | Reply | Reply With Quote | Top
Anthea
guest
May-20-03, 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 Printer-friendly page | Edit | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

67083886