|
uchinyan |
|
いろいろと進みましたね。しかし，難問であることがより明確になった感じかなぁ。
#41135 けーすけさん，一応理解できたと思います。これで「ある程度」は正しそうな値が得られそうですね。 しかし，やはり概算の計算であり，またその個数のパターンが得られる保証はないので， 「ある程度」でしかないようです。 実際，n = 8 のとき 25 個になりますが，いろいろやってみても 24 個のパターンしか見つかりませんでした。 どうしたものか，と思っていたのですが．．． #41140 スモークマンさん，検索及び情報提供をありがとうございます。 おっしゃるように，どうやらこれで間違いないようですね。 ということは，やはり，n = 8 は 24 個のようですね。 #41141，#41142 Ｊママさん，そう，私も何らかの規則性が比較的容易に見つかるのではないか，と思ったのですが， ２次元なので意外なところに長方形ができていたりして，そう簡単ではないようです。 #41144 こちらは，後で時間を見つけて読んでみますね。 いずれにぜよ，所詮，単純なルールなので，注意深く調べれば何らかの規則性は見つかりそうな気もするのですが．．． ただし，このアプローチでのパターンが最大個数を与える，ということは，別途，証明する必要があります。 最初の n * n の対角線上の並びは，どの行にもどの列にも碁石が一つしかない最大個数の並びです。 そこで，これに一つ碁石を追加すると，辺がマス目を描く直線と平行な長方形の半分が得られます。 こうして長方形にならないように順次碁石を置いていくのがこのアプローチの本質なのですが， いつかは別なところに長方形が現れるので難しいわけです， それと，出発点の，どの行にもどの列にも碁石が一つしかない最大個数の並び，は，対角線だけではありません。 このアプローチを取る以上は，違う出発点の並びでも同じような規則氏があって？，結局は同じ個数以下が得られる， ということを示す必要があります。 もっともこれは，考えてはいませんが，行や列の入れ替えで何とかなるのかも知れません。 まぁ，当面はこのことは後てもよく，対角線から始めるアプローチで何か分からないのかなぁ．．． もっとも目から鱗の解法があればうれしいのですが，スモークマンさんの情報からすると，どちらも難しそうですね。 |
|
ネコの住む家
11月23日（土） 14:13:51
41146 |