数論では数少ない、きちんと整理された解法、平方剰余 (Legendre’s/Jacobi’s symbols) の応用問題があった。

ACM問題 #10831 Gerg’s Cake
意訳: パーティを披こうとした。p人の友達が到着したけれど、遅刻者はまだ a人もいる。長く待たせるのも悪いので、正方形のケーキを先着者にご馳走させようと考えた。遅刻者のa人分を残しながら、ケーキを p人で平等に分けたい。ただし、ケーキの一切れはまた正方形に切らないといけない。果たしてそんな切り方は可能だろうか。

<注意> 問題の記述文の、最初のパラグラフ(段落)のところに、p は合成数でないことが書いてある。言い換えると、p が1または素数だ。

例:先着者5人、遅刻者1人だとすると、ケーキを16等分の正方形にし、先着者はひとり3切れ食べられることになる。先着者3人、遅刻者1人なら、ケーキを4等分にすればOK。

上の話しはもちろんつぎの数式に合わせて書き上げられたものだろう。

  X2 = a + n*p

a と p はそれぞれ、遅刻者と先着者の数。n、X は非負の整数。

さて、式の両辺を p で割ると、

  X2 = a (mod p)

の形になり、平方剰余の計算に帰着される。

平方剰余のことは 既に他のところに書いた。つまり、奇素数 p と、 p で割りきれない a に対して、

    X2 ≡ a (mod p)

なる X が存在するときに、a を mod p での平方剰余といい、そんな解 X がないときは、平方非剰余という。解 X があるかどうかの判定 は効率的にできる。

ただ、上記の平方剰余の計算関数(解の存在を判定する関数)では、前提として、

  p は奇素数でなければならない。また、
  a は p で割れないものでなければならない。 

の2点があるので、ここでは、前提に合わない a と p をリストアップして、個別に考える。

  (1) p が偶素数(つまり2)、
  (2) p が 1、
  (3) a は p で割り切れるもの。

(1) については、もとの数式が X2 = a + 2n になるので、任意の奇数値の a に対しは、奇数の X を選び、任意の偶数値の a に対しては、偶数の X を選べば、整数 n が必ず存在することが判る。

(2) についても簡単に n が存在することが判る。なぜなら、 X2 = a + n という式になるので、n = X2 – a となる n が必ずあるからだ。

(3) については、a が p の倍数になるので、 a = mp とすると、X2 = (m+n) p になる。X を p の倍数、例えば、X = kp として選べば、 m+n = k2 p になるので、整数 n が必ず存在するわけだ。

前提に合わない a と p はすべて解をもつことが以上の分析で判っただろう。

最後に、参考のため、C言語プログラムをのせておく。
p10831.c

Comments are closed.

Post Navigation