DouKaku? 4371 kozima: いい方法が思いつかなかったため多重ループ...(正しい文(クイズ))

Comment detail

いい方法が思いつかなかったため多重ループ生成 & eval してしまいました。

入る数字は n=2 なら 8 未満、n>2 なら n^2 未満と評価できました。
というわけで理論上は停止性を保障できています。

;; format の部分はもっときれいにやる方法がないものでしょうか……

(defun bound (n) (if (= n 2) 8 (* n n)))

(defun solution-p (n &rest nums)
  (let ((s (format nil (format nil "~~{~~~DR~~}" n) nums)))
    (loop for i from 0 below n and a in nums
      unless (= (1- a) (count (digit-char i n) s)) return nil
      finally (return t))))

(defun gen-solver (n i bound chars vars)
  (if (= i n)
      `(if (solution-p ,n ,@vars)
           (format t "この文は~@?あります~%"
                   (format nil "~~@{~~Cが~~~DR個~~^，~~}" ,n)
                   ,@(apply #'nconc (mapcar #'list chars vars))))
    `(loop for ,(nth i vars) from 0 below ,bound do
       ,(gen-solver n (1+ i) bound chars vars))))

(defun solve (n)
  (let ((code (gen-solver n 0 (bound n)
                          (loop for i from 0 below n collect (digit-char i n))
                          (loop repeat n collect (gensym)))))
    ;; (eval code)
    (funcall (compile nil (eval `(lambda () ,code))))
    ))

n>2 のときは n+2 未満しか入らないかな？あと、文に表れる数字の個数を使って枝刈りできますね。これで n=8 のときが1分で終わりました。 n<=8 での出力結果はすべて shiro さんの #4367 と同じです。

(defun bound (n) (if (= n 2) 8 (+ n 2)))

(defun check (n &rest nums)
  (<= (reduce (lambda (s x) (+ s (- x (floor (log x n)) 1))) nums
              :initial-value 0)
      n))

(defun solution-p (n &rest nums)
  (let ((s (format nil (format nil "~~{~~~DR~~}" n) nums)))
    (loop for i from 0 below n and a in nums
      unless (= (1- a) (count (digit-char i n) s)) return nil
      finally (return t))))

(defun gen-solver (n i bound chars vars)
  (if (= i n)
      `(if (solution-p ,n ,@vars)
           (format t "この文は~@?あります~%"
                   (format nil "~~@{~~Cが~~~DR個~~^，~~}" ,n)
                   ,@(apply #'nconc (mapcar #'list chars vars))))
    `(loop for ,(nth i vars) from 1 below ,bound
       ,@(if (> n (1+ i)) `(while (check ,n ,@(subseq vars 0 i))) ()) do
       ,(gen-solver n (1+ i) bound chars vars))))

(defun solve (n)
  (let ((code (gen-solver n 0 (bound n)
                          (loop for i from 0 below n collect (digit-char i n))
                          (loop repeat n collect (gensym)))))
    ;; (eval code)
    (funcall (compile nil (eval `(lambda () ,code))))
    ))

「かな？」とか言ってますが、一応計算して出した評価なので
どうやって出てきたか書いておきます。

正しい文に現れる数字の個数は次の二通りに表せます。
1. Σ"k が現れる回数"
2. n + Σ("k が現れる回数" の n 進での桁数)
そこで k が現れる回数を a[k], その桁数を f[k] とすると
(*) Σ(a[k]-f[k]) = n

これと a[k] >= f[k] から各 k について a[k] - f[k] <= n
左辺は単調増加なことから適当に計算して
 n=2 なら a[k] <= 5
 n>2 なら a[k] <= n + 2
が出ます。

あと n>2 で n+2 が入らないことの確認も。
a[k] = n+2 = 12(n) だと a[k]-f[k] = n なので (*) から
i!=k のとき a[i]=f[i] が必要で、これを満たすのは a[i]=1 だけ。
つまりひとつの数字を除いて一回しか現れないということですが、
12 が出てくる以上これは不可能です。

n >= 7 の場合は以下の２つしかない。

「この文は0が1個, 1が11個, 2が2個, 3が1個, 4が1個, ...,
  (n-1)が1個あります。」
「この文は0が1個, 1が(n-3)個, 2が3個, 3が2個, 4が1個, ...,
  (n-4)が1個, (n-3)が2個, (n-2)が1個, (n-1)が1個あります。」


長いです。ややこしいです。証明に抜けがないとよいですが・・・

kozimaさんの#4374の表記に合わせて i が現れる回数を a[i] と書きます。

■(A) すべての i に対して a[i] <= n+1

kozimaさんの#4374による。

■(B) k != 1 ならば a[k] < n（つまり a[k] は１桁）

(A) より各 a[i] は１桁か、上位桁の数字が 1 の２桁。
よって 1 でない i は１の位にしか現れる可能性がないので a[i] <= n+1
以下、k は 1 でないとする。
(i) ある k で a[k] == n+1 とするとすべての i に対して a[i] == k。
  これは a[k] == n+1 に反する（k < n だから）のでダメ。
  よってすべての k に対して a[k] <= n。
(ii) ある k で a[k] == n とすると k 以外の i に対して a[i] == k。
  （ただし k が 0 の場合は a[i] = 10（n進））
  ここで 0 でも 1 でも k でもなく a[1]（最大２桁）にも出てこない数字 j
  （n >= 7 なのでそういう数字は存在する）を考えると j は「□個」の部分には
  現れず「□が」の部分に１回だけ現れるので a[j] = 1。
  これは a[j] == k に反する（k != 1 だった）のでダメ。
よってすべての k に対して a[k] < n （つまり１桁）

■(C) a[1] == 11（n進）== n+1 のときは
「この文は0が1個, 1が11個, 2が2個, 3が1個, 4が1個, ...,
  (n-1)が1個あります。」

a[1]（== 11（n進））には 0 が現れず a[i] (i != 1) にも (B) により 0 は現れない
（「0個」はありえない）から「この文は0が1個, 1が11個,」まで確定。
ここまで 1 は４回現れたので残り n-3回。
ということは１箇所だけ「1個」ではなく（これが「kは□個」だったとする）それ以外は
すべて「1個」のはず。
k の出現が１回にならないようにするには「kは□個」の「□」の場所に k が現れるしかない。
つまり「kはk個」。このつじづまがあうのは k == 2 の場合だけ。

■(D) a[1] == 10（n進）== n はありえない。
a[1]（== 10（n進））には 0 が１回現れ a[i] (i != 1) には (B) により 0 は現れない
（「0個」はありえない）から「この文は0が2個, 1が10個,」まで確定。
ここまで 1 は２回現れたので残り n-2回。
ということは残り（2の回数も含む）はすべて「1個」。しかし 2 が「2は」と「0は2個」
の２回すでに現れているのでダメ。

(A)(C)(D) から
■(E) 「この文は0が1個, 1が11個, 2が2個, 3が1個, 4が1個, ..., (n-1)が1個あります。」
のケース以外のときはすべての i に対して a[i] < n（つまり１桁）。さらに「0は1個」

「0個」はありえないので 0 が現れるのは「0は」の１箇所だけ。

以降はすべて１桁のケースのみを考える。

■(F) Σi*(a[i]-1) = 数字の総出現回数 == 2*n

すべて１桁なので。

ここからが本番。
■(G) 4 から上で「1個」以外が現れるのは最大１箇所。

もし２箇所以上で「1個」ではなかったとすると x = min {i | i >= 4, a[i] > 1} と
それとは別の場所の y（> x >= 4）で a[x] > 1, a[y] > 1。
a[x] > 1 なので「xは」以外に「x個」がどこかに現れる。
「0は1個」なので「0はx個」はありえない。
仮に「1はx個」として現れたときは「y個」の方をどこに現れるか考える。
以下の考察は x,y の大小は関係せず対称なので「1は□個」に現れない方を x とする。
よって「x個」は 2 より上の場所に現れる。
例えば「2はx個」として現れた場合を考える。x >= 4 なので 2 は４回以上現れる
「2は」で１回現れているのを除外すると「2個」として３回以上現れる。
「0は2個」と「1は2個」はありない。
（0 に関しては「0は1個」から。1 に関しては「1個」の数が少ないと (F) の左辺が
n^2オーダになるため）
もし「3は2個」でなかったら 4 より上に「2個」が３回以上現れる。
「3は2個」の場合「2個」の登場が一つ減るが今度は「3個」の登場（「1は3個」もありない）
を加味して、合わせて 4 より上に「2個」または「3個」が３回以上現れる。
どちらにしても 4 より上に「1個」でないのが３回以上現れる。
すでに x,yとして２箇所を除外しても別の場所 z に「1個」でないのが現れる。
z > x >= 4 なので z >= 5。
先ほどの x,y の代わりに y,z（>= 5） で考えると 4 より上に「1個」でないのが
（今度は）４回以上現れる。
すでに x,y,zとして３箇所を除外しても別の場所 w に「1個」でないのが現れる。
w > z >= 5 なので w >= 6。
ということを無限に繰り返せることになるが有限なので無理。

■(H) 4 から上がすべて「1個」はありえない。

4 から上がすべて「1個」とする。
1 の出現回数は 4 から上がすべて「1個」の (n-4）回と「0は1個」の1回と
「1は」の1回を合わせて最低 (n-2)回。
1 の出現回数を m とすると m >= n-2 > 4 なので m の出現回数は1個。
これは「mは」と「1はm個」の最低2個現れることに反する。

■(I) 4 から上に「1個」以外が１箇所だけ現れるのは
「この文は0が1個, 1が5個, 2が3個, 3が2個, 4が1個, ...,
(n-4)が1個, (n-3)が2個, (n-2)が1個, (n-1)が1個あります。」

1 の出現回数は 4 から上で一つだけ例外がある「1個」の (n-5）回と「0は1個」の1回と
「1は」の1回を合わせて最低 (n-3)回。
1 の出現回数を m とすると m >= n-3。
「2がm個」や「3がm個」はありえない（2 や 3 が m個現れる余裕はない）ので
m の出現は「1がm個」と「mが」の２箇所だけで「mが2個」。
よって 2 の出現回数は２回以上になるが「2が2個」ではさらに 2 がまた出てきて
数が合わなくなるので可能性があるのは「2が3個」。
「この文は0が1個, 1がm個, 2が3個, 3が2個, 4が1個, ...,
(n-4)が1個, (n-3)が2個, (n-2)が1個, (n-1)が1個あります。」
で 1 以外のつじつまは合うので最後に 1 の数を合わせて「1が(n-3)個」。

以上。

あー、自己参照問題はややこしいー。
(G) はもしかしたら対角線論法とか使ってもっと簡単に証明できるかもしれない。
（誰かお願い）

示そうとしてたんですが、先を越されました。
方針はだいたい同じで (F) までは出たんですが (G) ができなくて……
丁寧に場合分けしていけばよかったんですね。

ところで (G) の別証明を考えていたら雰囲気の違う方法が見つかりました。
a[1] >= 4 は仮定して、二桁の値を含まない解が一意なことを示します。

天下り式ですがとりあえず定義。
b[i] := (i-2)*(a[i]-1)
S := b[3] + b[4] + ... + b[n-1]
S' := S - b[a[1]]

■(F') S = -b[1] = a[1] - 1

Σi*(a[i]-1) = Σa[i] = 2*n から少し計算すると Σb[i] = 0 が出る。
b[0]=b[2]=0 なので b[1] を移項すれば求める式が出る。

■(J) a[a[1]] = 2, S' = 1

(F') に S = S' + b[a[1]] を入れて計算すると S' + (a[1]-2)*(a[a[1]]-2) = 1
a[1] は「1がa[1]個」に現れるので a[a[1]]>=2 であり、また a[1]-2 >= 2 だから
左辺第二項は 0 または 2 以上。さらに S' も非負だから主張が従う。

■(K) i>3, i!=a[1] のとき a[i]=1 であり、また a[3]=2

(J) より S' = 1 となるが、 i>3 なら b[i] は 0 または 2 以上。
したがって b[3]=1, それ以外の i では b[i]=0 でなければならない。

これで a[1], a[2] 以外は確定します。あとは難しくないでしょう。

エレガント！
Σ（ほとんど非負）== 0 を作るのが見事ですね。

Σ(i-2)*(a[i]-1) の式に意味的背景はあるのでしょうか。

やっぱり「どこから出てきたの？」って気はしますよね。意味はよく分かりませんが、なんとなく a[1] の大きさを評価すればいいんじゃないかと思って

a[1] = なんかa[1]を含まない式

みたいにできないかなと思っていたら気が付きました。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq