|
2006年08月01日(火)
離散必修 |
勉強しまくりですよあなた。離散数学中心でまじでやってますよ。ほんとしにますよ。というより死んでますよ。っていうか死にましたよ。てんぱりまくりですよ。
離散数学の問題は例えばこんなの。答えを暗記してしまったものを書くしかない！
■位数5の完全グラフが平面グラフでないことを示せ。示しなさい。示してください。示せるかどうか試みてください。
仮に，平面グラフだとしよう。位数5の完全グラフなんだから点の数5，枝の数は10あるはずだ。あるに違いない。とすると，オイラー定理より
f+5=10+2
より領域f=7あるはず。ってことは辺の数は7*3/2=10.5=11なきゃいけないんだけどないので矛盾。よって平面グラフではない。と思う。
■どんなグラフにも次数の等しい２点が存在することを示しなさい。
確かこれはだな。位数をnとする。どの点の次数も0〜n-1のどれかのはず。とすれば，グラフ内で0とn-1が同時に発生することはありえない。よって鳩ノ巣原理より次数の等しい2点が存在。
■奇次数の点は偶数個あることを示しなさい。
場合わけ。
・今グラフのすべての点の次数を0だとする。このときは奇次数の点の数は0より偶数個。
次に0か0じゃないとき。このとき1枝加えることを考える。
・加える枝の両端点が偶次数ならそれらは奇次数になり，逆に奇次数なら偶次数になる。すなわち偶次数の点の数は２変化することがわかる。
・一方の端点が偶次数，もう一方が奇次数なら１本加えても次数の偶奇性は変化しない。
■テニスしなさい。
これはよんでもわからないし暗記も無理だし…無理ぽ。
■あるパーティーで僕はもてないので絶対にありえませんがビジャクーとその彼女を含めた3組のカップルがきています。みんなで握手しました。このとき自分の彼女とは握手しないで，自分自身とも握手しませんでした。ビジャクーが何回握手したかをそれぞれにきいたところ，みんな異なる回数をこたえました。さてビジャクーとビジャクーの彼女は何回握手した？
これは簡単。
６回握手した人がいる。問より０回握手した人がその人の彼女か彼氏。
５回握手した人がいる。１回握手した人がその人の彼女か彼氏。
４回握手した人がいる。２回（ry
３回握手し（ry。３回（ry
ここでみんな異なる回数をこたえたとあるからビジャクーは３回握手した人。よってビジャクーとその彼女は３回握手している。
■数学的帰納法
初期命題で成立したことを示し，次にkで成立すると仮定してk+1でも成立するようにk+1を代入して式変形する。
■オイラーの定理
n以外のnの約数で素数であるものをP1〜Pkとするとき，
@(n)=n(1-(1/P1))*...*(1-(1/Pk))
これ以外にもいろいろ問題があるんだけど，とにかくこのへんはもうばっちり。これ以外から問がでる可能性だってあるんだからなんとかしないと…。
やばい！とにかく離散数学は必修だから絶対にとらないと。
ではでは。 |
|
