I think I've heard that one before NS. I don't think I was satisfied with the solution though.

Ok, not the same riddle I heard. That's pretty airtight.

(I'm going to refer to the sage at the back of the line as #1)

If #1 looks at 2 and 3 and they have different coloured hats, we'll say white and black, then he says "red" which neither are wearing. #2, seeing 3's black hat, knows that his hat must be white, and says so. This cues #3 that his is white, which he says.

If 2 and three had the same color hat (i.e., red), #1 says "red" again. #2, seeing 3's red hat, knows that his is also red, and says so. This tell #3 that his is also red.

At worst, 34 sages die.

I know, I was about to edit to say I was working on it. Give me a minute to type it out.

EDIT:

#1 is going to be looking at 2, 3, and 4. We have to examine 5 cases. (I will put a theoretical set up in parenthesis)

a) All three hats are the same (RRR). #1 says "red". #2, seeing 2 red hats in front of him, knows his is also red. #3 Hearing 2 reds and seeing a red in front of him also says red. #4 in turn says red.

b) All three hats different (RBW). #1 says "red". #2 seeing no red hats in front of him, realizes that all hats are different and says red. #3 sees a white hat and hearing two reds know this means all the same or all different, so he says black. #4 says white.

c) Two and One, #2 different (RWW). #1 says "black". #2 seeing two white hats knows if his hat was white, he would have heard "white", so he knows his is the opposite and says "red". #3 knows that they aren't all wearing black, and aren't all different (else #2 wouldve said "black"), so seeing white, he knows he is also white. #4 also says white.

d) Two and One, #3 different (RWR). #1 says "white". #2 then knows his hat is not black, (scenario b). Seeing white and red ahead of him, he know his hat is the opposite of what was said, as says "red". #3 hearing different colors knows that all hats are not the same, and are not all different. He know he is the odd man out, red ahead and red behind, so as the initial cue was white, he is white. #4 states his color red.

e) Two and One, #4 different (RRW). #1 again says "white". By the same logic as in d, #2 knows he is red. #3 again know it is a two and one situation. He knows that #4 is the odd man out this time, or else "black" would have been said by #1. Therefore he knows he is red. #4 knows he is the odd man out, and picks the initial color, white.

At worst, 25 sages die.

Dr. Jeebus wrote:

The king arranges 100 sages in a line. The 100 sages then bumrush the single king. I'd be surprised if the king takes out 3 of them before being killed.

You've never tried to attack the King in Ultima.