平成２３年１月３０日

[流れ星]

　　　　　第２５２回数学的な応募問題解答

　　　　　　＜解答募集期間：1月9日〜1月30日

［２種類のタイルで］

ここに、1辺の大きさが３と４の２種類の正方形のタイルが合わせて2011個あります。これらのタイルをうまく利用して、1辺の大きさがＭの正方形の床にびっしりと隙間まく敷き詰めることが可能かどうか考えてください。もし、可能なら大きさMの値と、２種類のタイルをそれぞれ何個利用したかを教えてください。

　また、1辺の大きさがＭの正方形の床を1辺の大きさが３と４の２種類の正方形のタイルで敷き詰めることが可能ならば、Ｍのもつ条件を考えてください。

＜水の流れ：「ピーター・フランクルの中学生でも分かる大学生にも解けない数学問題集�A」から改題して出題しました。敷き詰めることが可能な場合どのようにして2011個のタイルを張っていくかは私には一部の場合しか分かっていません＞

ＮＯ１「uchinyan」 01/10 13時33分受信

「uchinyan」 01/16 15時43分受信

　　　「uchinyan」 01/30 14時39分受信 更新1/30<br>

今回の問題は，ある程度までは解けたものの，敷き詰めパターンの網羅までは行っていません。恐らく，試行錯誤かプログラムかにより実際に調べないとダメだと思いますが，

これは，大変そうに思うのと，ちょっと時間が取れないので，割愛させてください (^^;

一辺 3，4 の正方形の個数を x 個，y 個，x，y は 0 以上の整数，とすると，

個数の総数，x + y = 2011

面積，9x + 16y = M^2

さらに，一辺 3，4 の正方形は一辺 M の正方形の辺に対して傾くことは不可能，

つまり，一辺 3，4 の正方形の辺は一辺 M の正方形の辺に平行でなければならない，ので，

a，b を 0 以上の整数として，

M = 3a + 4b = 正の整数

と書けます。したがって，

9x + 16y = 9x + 16 * (2011 - x) = 16 * 2011 - 7x = M^2 = 平方数

0 <= x <= 2011 なので，

9 * 2011 <= M^2 <= 16 * 2011

134.532… = 3 * sqrt(2011) <= M <= 4 * sqrt(2011) = 179.376…

135 <= M <= 179

一方で

x = (16 * 2011 - M^2)/7

が整数となるには，M を 7 で割った余りが 2 又は 5 でなければならないので，

M，x，y の候補として，次の 13 組が考えられます。

(M,x,y) =

(135,1993,18), (138,1876,135), (142,1716,295), (145,1593,418), (149,1425,586),

(152,1296,715), (156,1120,891), (159,985,1026), (163,801,1210), (166,660,1351),

(170,468,1543), (173,321,1690), (177,121,1890)

これらをさらに絞り込みます。これには，

M = 3a + 4b

をさらに詳細に調べます。

まず，一辺 M の正方形の横の辺を長さ 1 ずつに区切り，

左端から 0, 1，2，...，i，...，M-2，M-1，M と番号を付けます。

そして，一辺 3 の正方形の内部の一部が一辺 M の正方形の内部に含まれていて，

一辺 3 の正方形の左端の縦の辺，一辺 M の正方形の横の辺に垂直です，が，

i の位置にある個数を a(i) とします。

定義より，a(M) は意味がないですが，a(M-2) と a(M-1) は意味があって，

a(M-2) = a(M-1) = 0 です。また，便宜上，a(-2) = a(-1) = 0 としておきます。

すると，M = 3a + 4b はどの i に対しても成立しているので，

i の位置については，M = 3(a(i-2) + a(i-1) + a(i)) + 4b

i+1 の位置については，M = 3(a(i-1) + a(i) + a(i+1)) + 4b'

そこで，

3(a(i-2) + a(i-1) + a(i)) + 4b = M = 3(a(i-1) + a(i) + a(i+1)) + 4b'

3 * (a(i-2) - a(i+1)) = 4(b' - b)

3，4 は互いに素なので，

a(i-2) - a(i+1) = 4 の倍数

これより，M は自然数なので，k を自然数として M = 3k-2，3k-1，3k ですが，

M = 3k-2 の場合

a(0) = (a(0) - a(3)) + ... + (a(M-4) - a(M-1)) + a(M-1) = a(M-1) + 4 の倍数

M = 3k-1 の場合

a(0) = (a(0) - a(3)) + ... + (a(M-5) - a(M-2)) + a(M-2) = a(M-2) + 4 の倍数

と書けます。ところが，a(M-2) = a(M-1) = 0 だったので，

M = 3k-2 の場合，a(0) = 4 の倍数

M = 3k-1 の場合，a(0) = 4 の倍数

つまり，

M が 3 の倍数でないときは a(0) は 4 の倍数

になります。そこで，

M = 3 * a(0) + 4b''

より，a(0) が 4 の倍数ならば，M も 4 の倍数です。

したがって，M は 3 の倍数か 4 の倍数でなければなりません！

この条件を使うと，先ほどの候補は，さらに，

(M,x,y) =

(135,1993,18), (138,1876,135), (152,1296,715),

(156,1120,891), (159,985,1026), (177,121,1890)

の 6 個に絞り込めます。さらに絞り込めるかですが．．．

実は，これら 6 個のうち (177,121,1890) 以外は実現が可能です。

以下の実現方法は，水の流れさんからのメールで頂いたヒントを基にしたものです。

M は 3 の倍数か 4 の倍数ですが，特に，その最小公倍数である 12 に注目します。

そして，まず，一辺 12 の正方形で敷き詰めることを考えます。

一辺 12 の正方形は，一辺 3 の正方形 16 個，又は一辺 4 の正方形 9 個，で実現可能なので，

必要に応じて，

一辺 3 の正方形 16 個 <---> 一辺 12 の正方形 1 個 <---> 一辺 4 の正方形 9 個

の置き換えをします。

さて，まず，先ほどの 6 個の候補のうち，M = 156 となっている (156,1120,891) に注目します。

M = 156 = 12 * 13 なので，これは，一辺 12 の正方形 13 * 13 = 169 個で実現できます。

もしこれが，すべて一辺 3 の正方形で構成されていたら，16 * 169 = 2704 個必要です。

ところが，x = 1120 個なので，2704 - 1120 = 1584 個多いです。

これが，先の一辺 4 の正方形への置き換えでうまく減らせればいいのですが，

可能ならば 1584/16 = 99 回の置き換えでできるはずで，

このとき，一辺 4 の正方形は 9 * 99 = 891 個になるはずですが，

確かに y = 891 になっており，実現可能なことが分かります。

特に，25 + 23 + 21 + 19 = 88 < 99 < 116 = 25 + 23 + 21 + 19 + 17 なので，

一辺 M の正方形の右端と下端から，一辺 12 の正方形を一辺 4 の正方形へ置き換えたもので，

一辺 M の正方形の右端と下端には，一辺 4 の正方形が 39 個ずつ(計 77 個)で，12 列，

一辺 M の正方形の左端と上端には，一辺 3 の正方形が 36 個，一辺 4 の正方形が 12 個，ずつ，

の場合を実現可能です。(中央の辺りは適当でいいです。)

なお，一辺 3 の正方形からなる一辺 12 の正方形は 169 - 99 = 70 個 残っています。

これを，(A) とします。

同様にして，一辺 12 の正方形 169 個をすべて一辺 4 の正方形で構成した場合からも，

一辺 3 の正方形への置き換え 70 回で同じことができますが，

特に，25 + 23 + 21 = 69 < 70 < 88 = 25 + 23 + 21 + 19 なので，

一辺 M の正方形の左端と上端から，一辺 12 の正方形を一辺 3 の正方形へ置き換えたもので，

一辺 M の正方形の左端と上端には，一辺 3 の正方形が 52 個ずつ(計 103 個)，12 列，

一辺 M の正方形の右端と下端には，一辺 3 の正方形が 12 個，一辺 4 の正方形が 30 個，ずつ，

の場合を実現可能です。(中央の辺りは適当でいいです。)

なお，一辺 4 の正方形からなる一辺 12 の正方形は 169 - 70 = 99 個 残っています。

これを，(B) とします。

以下の議論ではこれらを基にします。

次に，(152,1296,715) を考えてみましょう。

これは，(156,1120,891) よりも M が 4 少なくなっているので，

先ほどの (A) から右端と下端の一辺 4 の正方形を 1 列ずつ減らしてみます。

すると，891 - 77 = 814 個になりますが，814 - 715 = 99 個なので，

99/9 = 11 回だけ，一辺 3 の正方形に置き換えて戻してやればいいはずです。

そこで，(A) の一辺 4 の正方形への置き換え 99 回のうち 11 回を元に戻せばよく，

このとき，1120 + 16 * 11 = 1296 個で，確かに実現できます。

同様に，(138,1876,135) は，(156,1120,891) よりも M が 18 少なくなっているので，

先ほどの (B) から左端と上端の一辺 3 の正方形を 6 列ずつ減らしてみます。

すると，1120 - (103 + 101 + 99 + 97 + 95 + 93) = 1120 - 588 = 532 個になりますが，

1876 - 532 = 1344 個なので，

1344/16 = 84 回だけ，さらに一辺 3 の正方形に置き換えればいいはずです。

(B) では，一辺 4 の正方形からなる一辺 12 の正方形は 99 個 残っているので，

このうちの 84 個を一辺 3 の正方形に置き換えればよく，

このとき，891 - 9 * 84 = 135 個で，確かに実現できます。

(135,1993,18) も同様で，(156,1120,891) よりも M が 21 少なくなっているので，

先ほどの (B) から左端と上端の一辺 3 の正方形を 7 列ずつ減らしてみます。

すると，1120 - (103 + 101 + 99 + 97 + 95 + 93 + 91) = 1120 - 679 = 441 個になりますが，

1993 - 441 = 1552 個なので，

1552/16 = 97 回だけ，さらに一辺 3 の正方形に置き換えればいいはずです。

(B) では，一辺 4 の正方形からなる一辺 12 の正方形は 99 個 残っているので，

このうちの 97 個を一辺 3 の正方形に置き換えればよく，

このとき，891 - 9 * 97 = 18 個で，確かに実現できます。

一方，(159,985,1026) は，(156,1120,891) よりも M が 3 多くなっているので，

先ほどの (B) の左端と上端に一辺 3 の正方形を 1 列ずつ，合計 105 個，足してみます。

すると，1120 + 105 = 1225 個になりますが，1225 - 985 = 240 個なので，

240/16 = 15 回だけ，一辺 4 の正方形に置き換えて戻してやればいいはずです。

そこで，(B) の一辺 3 の正方形への置き換え 70 回のうち 15 回を元に戻せばよく，

このとき，891 + 9 * 15 = 1026 個で，確かに実現できます。

問題は，(177,121,1890) ですが．．．

(177,121,1890) は，(156,1120,891) よりも M が 21 多くなっているので，

先ほどの (B) の左端と上端に一辺 3 の正方形を 7 列ずつ足してみます。

すると，1120 + (105 + 107 + 109 + 111 + 113 + 115 + 117) = 1120 + 777 = 1897 個になりますが，

1897 - 121 = 1776 個なので，

1776/16 = 111 回だけ，一辺 4 の正方形に置き換えて戻してやればいいはずです。

このとき，確かに，891 + 9 * 111 = 1890 個になります。

しかし，(B) の一辺 3 の正方形への置き換えは 70 回なので，

さらに，111 - 70 = 41 回の一辺 4 の正方形への置き換えが必要です。

今は，一辺 3 の正方形を 7 列ずつ足しているのですが，

この配置では最大でも 27 個の一辺 12 の正方形しか取れないようで，

残念ながらうまくいきません。

他の配置が可能かどうかは確認できていませんが，少なくともこの置き換え手法では不可能で，実現は難しそうな感触です。

以上で，残った 6 個の候補のうち，

(M,x,y) = (135,1993,18), (138,1876,135), (152,1296,715), (156,1120,891), (159,985,1026)

は実現可能で，

(M,x,y) = (177,121,1890)

は実現不可能(そう)なことが分かりました。

もちろん，具体的な配置は今までの置き換えの手法だけでもどこを置き換えるかで変わってくるし，

上記以外の実現パターンの可能性はチェックしていないので，複雑になりそうです。

また，(177,121,1890) が実現可能かどうかは，難しそうな感触を得ていますが，

よく分かっていません。

ここらは，最終的にはプログラムに頼るしかないのかな，とも思います。

それは他の方にお譲りして，取り敢えずは，ここまでにしたいと思います。

なお，以上の議論から明らかですが，一辺 3，4 の正方形の総数が n 個の場合，

M^2 を 7 で割った余りは 0，1，2，4 なので，

n を 7 で割った余りが 0，1，2，4 のときしか解はありません。

そして，n がこの場合には，可能な M の候補は，[ ] をガウス記号として，

[3 * sqrt(n)] + 1 <= M <= [4 * sqrt(n)] のうち，

n を 7 で割った余りが 0 の場合，M を 7 で割った余りが 0

n を 7 で割った余りが 1 の場合，M を 7 で割った余りが 3 又は 4

n を 7 で割った余りが 2 の場合，M を 7 で割った余りが 2 又は 5

n を 7 で割った余りが 4 の場合，M を 7 で割った余りが 1 又は 6

で，さらに，

M は 3 の倍数か 4 の倍数

が，解の候補になります。

一辺 p，q，ただし p，q は互いに素，の正方形の総数が n 個の場合も同様ですが，

省略します。

(感想)

難しいです．．．年の最初から若干いい加減な解答で申し訳ないです。

M に更なる条件を付けられるか，具体的な配置の更なる構成手法はあるか，

プログラムでのチェック，そのアルゴリズムと計算量，など，

まだまだ課題は多いし興味は尽きませんが，

ＮＯ２「ｽﾓｰｸﾏﾝ」 01/14 12時51分受信

「ｽﾓｰｸﾏﾝ」 01/14 20時18分受信

「ｽﾓｰｸﾏﾝ」 01/18 01時00分受信 更新1/30

再考しました...^^;...Orz~

面積=3^2*a+4^2*b=M^2
a+b=2011 から…
9a+16b=M^2
9a+16(2011-a)=16*2011-7a=M^2
a=(16*2011-M^2)/7
16≡2, 2011≡2
M^2≡4　　mod 7 ならよいが…
7m±1,±2,±3…これらの2乗の7による剰余はそれぞれ…1, 4, 2
なので、M=7m±2 ならよい。
そのとき、a≡0　(mod 7)
a+b=2011≡2 になるためには…
b≡2
つまり…b=7k+2, a=7g
7g+7k+2=2011
7(g+k)+2=2011
7(g+k)=2009
g+k=287
a=7g, b=2011-7g…g≦287
このとき…
M^2=9a+16b=9*7g+16*(2011-7g)=2011*16-49g
たとえば…
√((2011 * 16) - (49 * 268)) = 138
√((2011 * 16) - (49 * 160)) = 156
google の計算機でひたすら探しました…^^;…
M=138 or 156 なら可能…?

a+b=k
9a+16b=M^2
9a+16(k-a)=M^2
(16K-M^2)/7=a
16≡2…M^2≡1, 2, 4
2k-M^2≡0 から…M≡2,4
k≡1 or 2
a+b=7g+1 or 7g+2 で、M=7t+2 or 7t+4 ならありえる。

*上の解は...地道に...google使って約300回程打ち続けました
きっと巧い方法があるんでしょうねぇ...?

「ｽﾓｰｸﾏﾝ」 01/28 14時10分受信 更新1/30

一応あれから考えたことは...
もし可能なら...2011は素数なので...
回転しても対称になってるはず...
角にはいずれかの正方形が嵌ってる...
４隅とも同じものか、対角が同じもの...
４隅とも同じもののとき...
内部も同じはず...
となると...中心に正方形があってm個(これ自体が点対称形)あって...2011-m=4k に
なってるはず...
k=502+(3-m)/4
m=4g+3=(n+1)^2-4 ならよさそう...
(n+1)^2-1=4g+6
n*(n+2)=2(2g+3)
n=2h
2h*(h+1)=2g+3 で駄目。
(n+1)^2-2=4g+3 なら...
(n+1)^2-1=4g+4 でOK。

対角が同じもののとき...
2011-m=2k
k=1005+(1-m)/2
m=2g+1
2g+1=(n+1)^2-4
2g+4=(n+1)^2-1
g が偶数ならOK。

2g+1=(n+1)^2-2
2g+3=(n+1)^2-1
g,n は奇数ならOK。

ここから考察できてませんし...意味のあることをしてるのかどうか...^^;?

ＮＯ３　「MVH」 01/29 13時21分受信 更新1/30

　

＜水の流れ：今回の問題は２０１１個ということで実際に敷き詰めが
具体的に私自身わかっていません。
ただ、最初、6個の組み合わせについては可能であること思っていました。

他の場合は分からないまま出題しました。
この点につて明快な答えのないままでしたことにお詫びします。

ところが、「MVH」さんの解答を拝見して後、再度考えてみました。

M＝１７７のとき、敷き詰めることができないと思い始めました。　
また、「ｽﾓｰｸﾏﾝ」さんの場合は判断しかねます。申し訳ないです。＞

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。