Clock Problem

So basically we have n clocks and each clock has k numbers (0 to k-1). n,k being natural numbers with n >= 2 and k >= 2.

We can only move the time on a clock by 1 forward every single move (If we move a clock by 1 when its at k-1 it goes back to 0). So basically our time on a clock is modulo k.

The question is, how many different combinations of clocks can you get without:

-Moving the time on the same clock twice in a row
Example:
If n = 3 and k = 3, we cant do:
0 0 0 -> 0 0 1 -> 0 0 2 as we moved the same clock twice in  a row. However doing,
0 0 0 -> 0 0 1 -> 0 1 1 -> 0 1 2 is aloud.

-Never having the same combinasion twice.
Example:
If n = 3 and k = 2:
0 0 0 -> 0 0 1 -> 0 1 1 -> 0 1 0 -> 0 0 0 doesnt work as we went back to 0 0 0 which is a combinasion we have already done.

We also start at 0 on each clock (it doesnt rly change the solution but just extra info).

Example:
If n = 2 and k = 2,
We have 0 0 -> 0 1 -> 1 1 -> 1 0 this is the max we can do so the answer is 4.

Answer

The problem is equivalent to the number of ways the number $k$ can be written as the sum of $n$ nonnegative integers with $2x_i \leq k+1$. This condition implies that we are not moving a click twice in a row. If the condition is violated, then $$𝑥_i≥⌈𝑘/2⌉+1. (1)$$ (here $⌈𝑘/2⌉$ is the smallest integer larger than $k/2$). So the total number of combinations without moving a clock twice in a row is the same as the number of nonnegative integer solutions to $$\sum_{i=1}^n 𝑥_𝑖=𝑘, x_i \geq 0 (*)$$ subject to $2𝑥_𝑖≤𝑘+1$. Apply the principle of inclusion-exclusion, where the $𝑛$ properties to be excluded are $2𝑥_𝑖≥𝑘+2$, equivalently, $𝑥_𝑖≥⌈𝑘/2⌉+1$. Without any constraints the total number of solutions of (*) is $C(𝑘+𝑛−1, 𝑛−1)$. Considering the constraints one at a time, the number of solutions violating (1) for some $1\leq i \leq n$ is $C(𝑘−(⌈𝑘/2⌉+1)+𝑛−1, 𝑛−1)$. It is not possible to satisfy (1) more than once. Putting all this together, the total number of solutions of (*) not violating (1) is $$C(𝑘+𝑛−1,𝑛−1)−C(𝑛,1)C(𝑘−⌈𝑘/2⌉+𝑛−2,𝑛−1)$$ $$=C(𝑘+𝑛−1,𝑛−1)−𝑛C(⌊𝑘/2⌋+𝑛−2,𝑛−1).$$
So the total number of different combinations of clocks is
$$\sum_{l=0}^{k}\left( C(l+𝑛−1,𝑛−1)−𝑛C(⌊l/2⌋+𝑛−2,𝑛−1) \right)$$
which is the answer to your questions.


You can check that for $n=2$ and $k=2$ this gives 4.


Next I explain why the number of nonnegative solutions of (*) without any constraint is $C(𝑘+𝑛−1,𝑛−1)$. Write the number $n+k$ as the sum of $n+k$ ones: \[n+k=1+1+1+\dots +1,\] there are $n+k-1$ $"+"$ signs above. In $C(n+k-1,n-1)$ ways we can choose $n-1$ "+" signs to remove and be left with $k-1$ "+" signs. If there are no "+" signs between numbers we just add them. Then we will get a solution to $$\sum_{i=1}^n y_i=k+n, \text{with} \ \ y_i \geq 1.     (**)$$ Subtracting $n$ from both sides and letting $x_i=y_i-1$, we get a solution to (*). So there is a one to one correspondence between solutions of (*) and (**).

Erdos Erdos
Judge
  • Leave a comment if you have any questions.

  • It took me a very long time to write this solution. Please consider offering much higher amounts for such high level questions, otherwise you may not get a response from other users.

The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to 50% commission on every question your affiliated users ask or answer.