アットランダム≒ブリコラージュ

17252：可約分数を既約分数にする...基本 ^^

ガラスが不透明にできるホテルがあったけど...^^;

問題17252・・・http://task.naganoblog.jp/c10960_7.html より 引用 Orz〜

解答

・わたしの...

ユークリッドの互除法で、約数が１でない...

(15n+2,14n+3)

=(n-1,14n+3)

=(n-1,17)

so...

n-1=17k

n=17k+1

(15(17k+1)+2)/(14(17k+1)+3)

=(15k+1)/(14k+1)

が既約分数ね ^^

17251：Σ計算...基本 ^^

一日中おれそう ^^

問題17251・・・http://task.naganoblog.jp/c10960_7.html より 引用 Orz〜

解答

・わたしの...

正方形の対角線を除いた格子点の数の半分ね ^^

(n^2-n)/2=n(n-1)/2

^^

↑

おかしかったです...^^; Orz...

↓

・鍵コメT様からのエレガントな解法 Orz〜☆

例えばn=3の場合，
(2,1),(3,1),(3,2)に対応するのは確かですが，
結論はその個数の「3」ではなく，i+jの合計3+4+5=12です．

格子点の分布が直線x+y=n+1に関して対称であることから，
i+jの平均はn+1であり，これを個数にかけたものが結論です．
n(n-1)(n+1)/2となります．

*わたしだったら...エレファントに...

i...j
2...1・・・1+2*1
3...1+2・・・1+2+3*2
...
n...1+2+...+n-1・・・1+2+...+n*(n-1)
Σ[k=1〜n]k(k-1)/2+Σ[k=1〜n]k(k-1)
=(3/2)Σ[k=1〜n](k^2-k)
=(3/2)(n(n+1)(2n+1)/6-n(n+1)/2)
=n(n-1)(n+1)/2
としか考えられませんですわ... ^^;v

17250：証明...1<=x,y<=13 の領域の格子点を53個選んだら、x,y軸に平行な長方形となる4点が選べる...

東京ってというか、ホテルに緑デコしてるのって...日本文化ならではなの？？？

海外行ったことないわたしなもので...^^;

飛行機フォビア...^^;;

問題17250(友人問)

xy座標平面上の格子点の集合Sを次のように定める

S={(x,y)|x,yは1<=x,y<=13を満たす整数}

Sから任意に53個の点を選び、それら53点から成る点集合をTとする

このときTからある4点を選べ、それら4点を頂点とし、各辺が、

x軸、y軸に平行な長方形が得られることを示せ。

解答

・わたしの...

52/13=4

縦、横軸にそれぞれ少なくとも4点ある...

縦2点、横1点は決まる...

残りの1点が9点のもの(x9)しかないとして...

最初の縦を残り11本から選んでも、その縦に(x11)のものがないとすると...残り8点のもの(x8)しかないとして...

10-7

9-6

8-5

7-4

6-3

5-2

4-1

残り3本目を選べば、必ず一致するものが選べる...?

so...13-[n/13]-11=0

2-[n/13]=0

n=26個の点でも可能？？？

↑

何を考えてたのやら ^^; Orz...

↓

・鍵コメT様からの図頂戴 Orz〜

意味がとれませんが，52個の点では題意の4点がとれないものがあります．

ooooxxxxxxxxx
oxxxoooxxxxxx
oxxxxxxoooxxx
oxxxxxxxxxooo
xoxxoxxoxxoxx
xoxxxoxxoxxox
xoxxxxoxxoxxo
xxoxoxxxoxxxo
xxoxxoxxxooxx
xxoxxxooxxxox
xxxooxxxxoxox
xxxoxoxoxxxxo
xxxoxxoxoxoxx 

*再考ぉ〜^^;v

ある縦に4個はあるので、それらの横12個から残り3個を重ならないような3*4個取れるわけなのね ^^
so...もう1個あれば、鳩ノ巣原理から、同じ横の位置のものがあることになるので、それら4点で長方形ができますのね♪

*最初、わたしゃ何をとち狂ってたのやら...^^;;

↑

これも怪しかったです ^^;; Orz...

↓

・鍵コメT様からのもの Orz〜

「4個の格子点を含む列がある」は問題なく正しいですが，
「その列の4個と同じ行について，それぞれあと3個を置く必要がある」ことは
明らかとは言えないと思います．

例えば次のように示すことができます．

Tの要素(x,y)のうち，x=kであるものの個数をa[k]とします．
a[k]個の格子点から2つを選ぶ選び方は，a[k]*(a[k]-1)/2通りであり，
k=1,2,…,13についてのその合計Xは，
X=(a[1]^2+a[2]^2+…+a[13]^2)/2-(a[1]+a[2]+…+a[13])/2
となります．

ここで，b[1]=b[2]=…=b[13]=1として，
(a[1]^2+a[2]^2+…+a[13]^2)(b[1]^2+b[2]^2+…+b[13]^2)
≧(a[1]b[1]+a[2]b[2]+…+a[13]b[13])^2
より，
a[1]^2+a[2]^2+…+a[13]^2≧(1/13)*(a[1]+a[2]+…+a[13])^2
であり，a[1]+a[2]+…+a[13]=53のときは，
a[1]^2+a[2]^2+…+a[13]^2≧(53^2)/13だから，
X≧(53^2)/26-53/2=53/26*(53-13)>2*40=80.
1〜13のy座標から2つを選ぶ選び方は，13C2=78(通り)であり，
Xはそれより大きいので，鳩の巣論法より，
「同じx座標の点2個の組のうちで，y座標が同じ組合せになる2組が存在する」
ことが言えて，この2組が題意の4点を与えます．

ちなみに，a[1]+a[2]+…+a[13]=52のときは，
a[1]^2+a[2]^2+…+a[13]^2≧(52^2)/13=52*4であり，
X≧52*2-52/2=26*3=13C2となっているので，
同じx座標の点2個の組で，y座標が同じ組合せになる2組がないなら，
「各x座標の点が4つずつで，同じx座標の2点の組合せには，
すべてのy座標2つの組が1回ずつ登場する」ことが成り立ちます．
すでに例示したものは，この性質を満たすことが確かめられますね．

*まだピンとこないわたし...^^;

13C2=78種類あるとして、

x座標が同じものがそれより+2個多いことが言えても,x座標が同じa(k)が3個の場合はできないと思うのですけど...?

・鍵コメT様からのもの Orz〜

まとめというか，補足として，19日1時ごろに提示した
「格子点52個で題意を満たさない場合」を見てみます．

この例においては，
x=1のとき，y=10,11,12,13で，2つのy座標の組合せは
{10,11},{10,12},{10,13},{11,12},{11,13},{12,13}の6個です．
x=2のとき，y=7,8,9,13で，2つのy座標の組合せは
{7,8},{7,9},{7,13},{8,9},{8,13},{9,13}の6個です．
x=3のとき，y=4,5,6,13で，2つのy座標の組合せは
{4,5},{4,6},{4,13},{5,6},{5,13},{6,13}の6個です．

以下同様に，各x (1〜13)に応じて，2つのy座標の組合せがそれぞれ6個でき，
全部で78個のy座標の組合せができます．
これらに共通のものがないので，
この配置では題意の4点はとれないことになります．

格子点が53個の場合には
・このような2つのy座標の組合せが80個以上得られる
・2つのy座標の組合せは78種類しかないので，同一の組合せが含まれる
・例えばx=7とx=9で2つのy座標の組合せ{3,10}が共通だとすると，
(7,3),(7,10),(9,10),(9,3)の4点が題意の4点．
という流れで，本問を証明することができます．

*自分の思い違いに気づけました ^^;; Orz〜

なんども丁寧なフォローいただきありがとうございました〜m(_ _)m〜v

・友人から届いたもの...

*鍵コメT様の通りでしたわ ^^☆