ここから本文です

離散数学、論理、単射についての問題です n を正の整数とする.0 以上の整数 x ...

lin********さん

2018/3/1400:11:14

離散数学、論理、単射についての問題です

n を正の整数とする.0 以上の整数 x と y で x + y < n を満たすものの組 (x,y) をすべて集め た集合をTn とする.

また,0 ≤ z < n(n + 1)/2 を満たす整数z をすべて集めた集合をNn とする.
後述する様々な関数 f : Tn → Nn に対して,f が単射であるかどうか,すなわち,次の条件 (*) が成立するかどうかを考える.

(*) すべての (x1,y1) ∈ Tn と (x2,y2) ∈ Tn に対して,f(x1,y1) = f(x2,y2) ならば, x1 = x2 かつ y1 = y2 が成立する.

(問題)
n > 0 に対して,次のように定義される f : Tn → Nn が単射であることを示しなさい
f(x,y) = (x+y)(x+y+1)/2 + x

この問題をお願いします。またどのように解いていくのか教えていただきたいです。

閲覧数:
27
回答数:
1
お礼:
50枚

違反報告

ベストアンサーに選ばれた回答

sp5********さん

2018/3/1400:45:42

条件(*)通りそのまま考えます。
色々x1,y1を入れて考えてみましたか?
x1+y1=0のとき (x1+y1)(x1+y1+1)/2=0,
x1=0しかありえないのでf(x1,y1)=0.
x1+y1=1のとき (x1+y1)(x1+y1+1)/2=1,
x1=0または1なのでf(x1,y1)=1,2.
x1+y1=2のとき (x1+y1)(x1+y1+1)/2=3,
x1=0または1または2なのでf(x1,y1)=3,4,5.
x1+y1=3のとき (x1+y1)(x1+y1+1)/2=6,
x1=0または1または2または3なのでf(x1,y1)=6,7,8,9.

こんな風に、x1+y1の値が変われば大きく値が変わるため、f(x1,y1)=f(x2,y2)ならば、x1+y1=x2+y2にならないといけないことは予測がつくと思います。まずはこれを証明します。
今の例に書いたように、x1+y1≠x2+y2なら、x1とx2をどう調節してもfの値が一致することはないと分かるので、それを数式で記述します。

f(x1,y1)=f(x2,y2)とし、x1+y1>x2+y2とする。
このとき、
f(x1,y1)-f(x2,y2)
=(x1+y1)(x1+y1+1)/2+x1-(x2+y2)(x2+y2+1)/2-x2
≧(x1+y1)(x1+y1+1)/2+0-(x2+y2)(x2+y2+1)/2-x2-y2
≧(x1+y1)(x1+y1+1)/2-(x2+y2)(x2+y2+3)/2
≧(x2+y2+1)(x2+y2+2)/2-(x2+y2)(x2+y2+3)/2
=1
>0
矛盾。
同様に、x1+y1<x2+y2のときもf(x1,y1)≠f(x2,y2)なのでf(x1,y1)=f(x2,y2)ならばx1+y1=x2+y2

よって、f(x1,y1)=f(x2,y2)とすると、x1+y1=x2+y2であり、
f(x1,y1)-f(x2,y2)
=x1-x2
より、x1=x2.

これとx1+y1=x2+y2よりy1=y2.


以上より、f(x1,y1) = f(x2,y2) ならば, x1 = x2 かつ y1 = y2 が成立する.

質問した人からのコメント

2018/3/14 01:08:33

わかりやすく説明していただきありがとうございます。

あわせて知りたい

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる