How to select an item from a set with constraints, and finding when the pattern repeats.

Question

I am trying to solve the following problem with constraints that are explained below.

Assume there are customers walking into a restaurant and you want to assign them to different waiters. With the waiters having the following weights.

W1  W2  W3  W4  W5
1   2   2   3   5

What this implies is that W1 will get the 1st customer in every sequence of customers, W2 and W3 will get one customer in every other sequence, W4 will get a customer in every 3rd sequence, and W5 will get a customer in every 5th sequence.

A new sequence is started after every waiter in the prior sequence has received a customer.

Below is also a sample of the distribution of the customers to sequences and waiters and after that a description of each sequence.

Seq  W1  W2  W3  W4  W5
 1   C1
 2   C2  C3  C4
 3   C5          C6
 4   C7  C8  C9
 5   C10             C11
 6   C12 C12 C13 C14
 7   C15
 8   C18 C19 C20
 9   C21         C22
10   C23 C24 C25     C25

1. SEQ1 - Assign to waiters with weight = 1
2. SEQ2 - Assign to waiters with weight = 1,2
3. SEQ3 - Assign to waiters with weight = 1,3
4. SEQ4 - Assign to waiters with weight = 1,2
5. SEQ5 - Assign to waiters with weight = 1,5
6. SEQ6 - Assign to waiters with weight = 1,2,3

The above table is flattened as follows:

Customer    W1  W2  W3  W4  W5
  1         X               
  2         X               
  3             X           
  4                 X
  5         X       
  6                     X
  7         X       
  8             X   
  9                 X
  10        X           
  11                        X
  12        X           
  13            X       
  14                X   
  15                    X
  16        X           
  17        X           
  18            X       
  19                X   
  20        X           
  21                    X
  22        X           
  23            X       
  24                X   
  25                        X

Now, given the just the customer number and weightings, is it possible to find which waiter to assign the customer to and is there a generic way of doing this with different weights and different number of waiters ?

Answer 1

Let $S_n$ be the total number of customers after $n$ sequences and $W_1$, $W_2$ ... $W_m$ be the weight of the waitors:

$$S_n=\sum_{i=1}^m\left\lfloor\frac{n}{W_i}\right\rfloor$$

You can prove it by considering each waitor separately. Each waitor contributes $\left\lfloor n/W_i\right\rfloor$ to the total. $S_n$ is just the sum of these integer divisions.

You noticed such systems are periodic. If a pattern has a period of $n$ sequence numbers, it also repeats every $kn$ sequence numbers where $k$ is any positive integer. Every waitor creates a pattern with a period of $W_i$ sequences. And the period of the system is just the smallest repeating interval for all waitors. We can conclude that the period is the lowest common multiple of all $W_i$. This gives you:

$$p=LCM\{1,2,2,3,5\}=30$$

You can then get the number of customers per cycle which is $S_p$. Note that since $p$ is divisible by all $W_i$, the terms do not need to be floored:

$$S_p =\sum_{i=1}^m\left\lfloor\frac{p}{W_i}\right\rfloor =\sum_{i=1}^m\frac{p}{W_i} =30/1+30/2+30/2+30/3+30/5=76$$

Now we can look at the more difficult problem of finding what sequence a customer $k$ belongs to. We'll denote this as $f(k)$. It can be characterised as the minimal function that satisfies:

$$k\leq S_{f(k)}$$

Finding a neat closed form formula for $f(k)$ would prove too difficult.

EDIT: Restricting the domain didn't seem helpful, especially for calculating by hand, so I've removed it.

Try this. Calculate: $$\left\lceil\frac{C\times p}{S_p}\right\rceil$$

This tends to be a very good estimate. If it doesn't get the right answer, usually you only have to increment it once or twice although sometimes more.