解説

結論から述べると、 $k$ が奇数であれば可能、偶数であれば不可能です。

偶数の場合、自身以外の手が奇数通りになってしまいますので、引き分けを除いた勝率を半分に出来ません。よって、勝ちやすい手と負けやすい手が出来てしまいます。 奇数の場合には、 $k$ 種類の手を円周上に等間隔に並べ、着目する手から見て時計回りに $180$ 度の範囲内にある手に勝てる、と定義すればよいです。 もう少し数学的に述べると、 $0$ から $k-1$ とナンバリングした手 $a,b$ に対して、$(a-b)$ $mod$ $k\leq(k-1)/2$ であれば $b$ の勝ち、と定めているのと等価です。

余談ですが、この「k-じゃんけん」は、じゃんけんの公平性を活かしながら、引き分けの確率を減らすことでより効率的に勝敗を決めることが出来ます （その分簡単さが減っていますが…）。では、 $3$ 人でじゃんけんする場合はどうでしょうか。上記のように勝敗を定義した「k-じゃんけん」において、 $3$ 人で勝負をしたとき、 引き分けとなってしまう確率は、 $k$ が正の無限大に発散する極限でどのような振る舞いを見せるか、（興味があれば）求めてみてください。

考察のポイント

①：自明な必要条件で絞り込む

$k=2$ で実験してみると、明らかに片方が勝ってしまうことに気づきます。 すると、奇数であることが必要条件であることに思い至りますが、ここで「実は十分条件でもあるのでは？」と考えて検証してみることが有用です。 （未証明で提出してみても本問題は通りますが、一般的にはやめましょう（と言っておきます）。）

②：平易な構成を考えてみる

今回、構築部分が200点にしてはやや難しかったかもしれません。 難しいのは、手の勝敗に矛盾が起きないようにしなければいけない、という点で、例えばある手から見て「勝てる手」を全くランダムに半分決めていくと、 どこかで矛盾が起きる可能性が非常に高そうです。 このように考えると、勝敗条件はシンプルでないととても構築をやっていられない、という感触を得ることが出来ます。 そこで、おそらく一番最初に思い浮かぶのは $0$ から見れば $1,2,3,...$ と順に「 $0$ が勝てる手」にしていく構成であり、実際にこれで成功します。 また、あえてやや高度に考えるならば、今回すべての手に対称性が成り立つと都合がよいため、どの手から見ても同じ形の勝利条件を考えるとよい、 という考察をすることも可能かもしれません。