line of mathematicians guess their own hat color out of c colors

There is a common problem in which a long line of N mathematicians are each given a hat that is either red or blue. They cannot see their own hat but can see all in front of time and can hear any response. They must state their own hat color from the back of the line forwards and no information may be passed besides their guess. They may have a planning session in advance. What is the maximum number of correct guesses can they guarantee?

The answer is (look away if you don't know) $N-1$.

If, instead of 2 colored hats, we use $c$ different colored hats, how many can we guarantee? Assuming $N>>c$

I believe the answer to be $N-c+1$ and have confirmed this for $c=2, 3$, and $4$. I believe this should be simple to prove by using the concept of "$x$ formulas allow you to solve for $x$ variables" but I am not well versed enough in pure mathematics to answer this.

Solution 1:

Assign each color a value from $0$ to $c-1$. The last person in line computes the value of the sum of all the colors in front of him, modulo $c$ and guesses that color.

Then the second-to-last person knows the sum of all the colors in front of him, and can thus figure out his color.

Each other person knows the sum of all the colors in front and behind him, excepting the last, and he knows the total including his color from the last person's guess, so he can figure his color.

So the value is still $N-1$.

Your intuition was it would take more guesses, but each guess can also contain more information. With two colors, there is $1$ bit of information in the guess, with $c$ colors, there are $\log_2 c$ bits of information in each guess.