# 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
- 182 views
- $9.00

### Related Questions

- Allocation of Price and Volume changes to a change in Rate
- Need Help with Piecewise Function and Graphing it
- Graph the pair of equations in the same rectangular coordinate system: Y=-2x ; y=-2
- Algebra Word Problem 1
- Discrete Math Question
- If both $n$ and $\sqrt{n^2+204n}$ are positive integers, find the maximum value of $𝑛$.
- I really can't figure out equations with a power of 2 in it, please solve these and explain every step as if I was a baby.
- Algebra problem