# 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 (**).

- answered
- 266 views
- $9.00

### Related Questions

- If both $n$ and $\sqrt{n^2+204n}$ are positive integers, find the maximum value of $𝑛$.
- Prove that language L = {a^p ; p is prime} isn't regular using Myhill-Nerode theorem.
- Show that the $5\times 5$ matrix is not invertable
- Discrete Math Question
- Linearly independent vector subsets.
- Closest Points on Two Lines: How to use algebra on equations to isolate unknowns?
- Algebra 1 Word Problem #3
- Compounding interest of principal P, where a compounding withdrawal amount W get withdrawn from P before each compounding of P.