4×4数独の最少置数

質問

先日数学セミナーの問題で、4×４の数独には最低でも４つの数字が分かってないとだめ、ということを証明する問題が出ていました。
複雑で証明が理解できなかったのですが、

　　　　　a(11)a(12)　b(11)b(12)
　　　　　a(21)a(22)　b(21)b(22)

　　　　　c(11)c(12)　d(11)d(12)
　　　　　c(21)c(22)　d(21)d(22)

と、各マスに未知数を振って、（各マスは1,2,3,4のみ）

として、
　　　　a(11)+a(12)+a(21)+a(22)=1+2+3+4=10
　　　　b(11)+b(12)+b(21)+b(22)=10
　　　　c(11)+c(12)+c(21)+c(22)=10
　　　　d(11)+d(12)+d(21)+d(22)=10
　　　　a(11)+a(12)+b(11)+b(12)=10
　　　　a(21)a+(22)+b(21)+b(22)=10
c(11)+c(12)+d(11)+d(12)=10
　　　　c(21)+c(22)+d(21)+d(22)=10
a(11)+a(21)+c(11)+c(21)=10
a(12)+a(22)+c(12)+c(22)=10
b(11)+b(21)+d(11)+d(21)=10
b(12)+b(22)+d(12)+d(22)=10

「求める未知数が16個にたいして12個しか式がないから、少なくとも4個既知でなければならない」
は解答になっていないででょうか。

回答No.2

alice_44 · ベストアンサー

１６元１２連立一次方程式ですから、
有理数解を求めるのであれば、
最低あと４個の条件が必要
(４個で足りるかは不明だけれど)
なのですが…

数独の場合、自然数解を求める問題で、
解に重複が無いとかの条件もあるので、
より少ない追加条件で解が決まらないか
には検討が必要です。
方程式の rank だけで済む証明では
ないと思います。

お礼

なるほど、3,3,3,1の解とかありました・・・。

回答No.3

alice_44

例えば、２元一次方程式 x - y = 8 は、
実数解や有理数解は不定(解空間一次元)ですが、
解が一桁の自然数であれば、(x,y) = (9,1)
に決まります。御質問の数独についても、
そういうことの検討が必要だろうと思われます。
数セミの解答が複雑なのも、そのためでしょう。

回答No.1

nag0720

a(11)+a(12)+a(21)+a(22)=10
b(11)+b(12)+b(21)+b(22)=10
c(11)+c(12)+c(21)+c(22)=10
d(11)+d(12)+d(21)+d(22)=10
この４つの式から、16個の数字の合計は40であることが分かります。

したがって、このことと、
a(11)+a(12)+b(11)+b(12)=10
a(21)a+(22)+b(21)+b(22)=10
c(11)+c(12)+d(11)+d(12)=10
の３つの式から、
c(21)+c(22)+d(21)+d(22)=10
が導かれます。

同様に、
a(11)+a(21)+c(11)+c(21)=10
a(12)+a(22)+c(12)+c(22)=10
b(11)+b(21)+d(11)+d(21)=10
から、
b(12)+b(22)+d(12)+d(22)=10
の式を導かれます。
（代数学でいうと、12個の式は一次独立ではない）

つまり、10個の式だけでも十分ですから「12個しか式がないから」とは言えません。