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.

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

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:

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.

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.

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?