N Coloured Blobs (1 Viewer)

[GoldyOrNugget]

N coloured blobs wander around in groups on an open plain. Each group has its own distinct colour, and all coloured blobs in a group share the same colour. Occasionally, two groups will bump into each other: each of the blobs in the smaller group will take on the colour of the larger group, and the two groups will merge. If two groups of equal size bump into each other, the 'mergee' is chosen at random.

A researcher monitors a coloured blob population. Initially, each blob is on its own (i.e. in a group of size 1) and has its own distinct colour. After a sufficient amount of time has passed, all the blobs have become part of one huge group of the same colour.

Let K be the total number of times that a blob changed its colour. A lower bound on K is N-1, if every blob is merged individually into the huge group, hence only changing colour once: from its initial colour to the colour of the huge group. Determine an upper bound on K that is as tight as possible.

 

[seanieg89]

Nice question, will have a crack in a few hours after my supervisor meeting.

 

[seanieg89]

I think that:

(n*log(n))/(2*log(2))

is an upper bound which is tight. (For n >= 2).

I shall check my working tonight and write up a proof if I am happy with it.

 

[GoldyOrNugget]

I agree with that answer.

 

[seanieg89]

View attachment singlesol.pdf

A quick note on the intuition behind the solution:

This sort of problem screams out binary decomposition, which led to finding a likely candidate for a tight bound by solving a recurrence relation. The rest was just verification.