Monday, June 22, 2015

Use queuing rates to solve the 150 year old mystery

Science magazine: If you have n schoolgirls, can you create groups of size k such that each smaller set of size t appears in just one of the larger groups? Such an arrangement is called an (n, k, t) design.
Let's forget about N, the number of school girls. Instead lets construct a queueing system that generates groups of size k in which no set of size t appear more than onece. How do we do that?

I have my machine on the left. The machine makes groups from the first k elements in the input queue. The input queue is formed from the original group of school girls selecting one at a time, but that selection is interleaved with school girls selected from groups already composed. But from the already composed group, I only grab them at a rate 1/t , in sequence as in first out revolves back into the queue. This rate divisor implies that school girls  becoming part of their second group will be split by t members, and when making their third group will be split by t^2 members, and so on. So as each school girls get revolved its rate divisor insures no duplicate t sets.



I continue this process until I have a selection of school girls in the bottom queue who have gone through the revolving queue some 1+1/t+1/t^2+1/t^3... and the total number of trips through the revolving queue equals the group size. I need enough of these selection such that they add up to a whole number..

Why does this not work?
From the article, Keevash established an answer:
In January 2014, Keevash established that, apart from a few exceptions, designs will always exist if the divisibility requirements are satisfied.

He is talking about a divisibility requirement of the three parameters, (N,g,t). But isn't that all I do up in my machine? Haven't I just established a divisibility requirement in the three variables?

Hyperbolics
We can see that cosh and sing right away:
cosh = 1/2 * t^[k/2] ( 1+ t^-k), and similar for sign. t^[k/2] are the number of groups we can make.

No comments: