離散数学講義ノート（代数系）

代数系のモチベーション 29 × 54 を求めよ. ax²+bx+c=0 を解け. How? 29 × 54 1416 145 1566 x = -b±√b²-4ac 2a Why? なぜ求まるのか. なぜ解けるのか. +,-,×,÷のような演算とは 数学的には一体何なのか? "+"とは何か? 3+4 は 7 (3,4) → 7 a,b∈Zについて, a+bは Z×ZからZへの写像とみなせる. structure 演算は集合上に構造を定める. algebraic system 数の演算に似た構造を持つ「集合と演算の組」を 代数系と呼ぶ.

群・環・体

二項演算 binary operation 集合Aについて, A×AからAへの写像○をA上の二項演算と呼び, ○((a,b))をa○bで表すとき, ○を演算子とか演算記号と呼ぶ. operator symbol of operation A×AからAへの写像○が すべてのa,b∈Aについてa○b∈Aをみたすとき, A is closed under ○ Aは○について閉じているという. 閉じている 閉じてない 例 +:N×N→R, +((a,b))はaにbを足した数(=a+b)とすると, どんなa,b∈Nでもa+b∈NだからNは+について閉じている. 例 -:N×N→R, -((a,b))はaからbを引いた数(=a-b)とすると, 3-5=-2∉NだからNは-について閉じていない.

演算を観察してみる 3x=4を解け. 3×x = 4 1/3×(3×x)=1/3×4 (1/3×3)×x = 4/3 1 ×x = 4/3 x = 4/3 3に掛けると1になる数 3の逆数を両辺に左から掛ける. 結合律 逆数の定義より1/3×3=1. 1を掛けても不変.

演算を観察してみる x+2=5を解け. x+2 = 5. (x+2)+(-2) = 5+(-2). x+(2+(-2)) = 3. x+ 0 = 3. x = 3. 2に足すと0になる数を 両辺に右から足す. 結合律 -2は2に足すと0になる数 0を足しても不変

群 集合G上の二項演算○が次の(1)~(3)をみたすとき, group Gと○の組(G,○)は群であるという. 文脈から判別できるときは (G,○)は"G"と省略 されることが多い. associative law (1)[結合律] すべてのa,b,c∈Gについて(a○b)○c = a○(b○c). identity (element) (2)[単位元eの存在] e∈Gが存在して,すべてのa∈Gについてe○a=a, a○e=a. inverse (element) (3)[逆元a'の存在] すべてのa∈Gについて, a'∈Gが存在して, a○a'=e, a'○a=e.

群 例 (Z,+)は群である. (1) (a+b)+c = a+(b+c) (2) 0+a=a, a+0=a (3) a+(-a)=0, (-a)+a=0 例 (Z,×)は群ではない. ※2の逆数はZにはないので 例 (Q\{0},×)は群である. (1) (a×b)×c = a×(b×c) (2) 1×a=a, a×1=a. (3) a×1/a = 1, 1/a×a=1. 例 (Q,×)は群ではない. ※0の逆元はないので 例 G:={☺, ☹}上の演算○を次のように定めると(G,○)は群である. ☺○☺=☹ ☺○☹=☺ ☹○☺=☺ ☹○☹=☹ ○ ☺ ☹ ☺ ☺ ☹ ☹ ☹ ☺ (1) (☺○☹)○☺ = ☹ ☺○(☹○☺) = ☹ (2) 単位元は☺ (3) a∈Gの逆元はa.

群 例 整数n,aについて, nを法とするaの剰余類[a]をaで表すことにする. G:={0,1,...,n-1}上の演算+を次のように定めると(G,+)は群である. a+b = a+b 例 n=6のとき 3+4 = 7 = 1 ※[1]も[7]も {...,-5,1,7,13,...}を表す. + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 (1) (a+b)+c = a+b+c = (a+b)+c = a+(b+c) = a+b+c = a+(b+c). (2) 単位元は0. (3) aの逆元はn-a.

演算を観察してみる 2(3x+1)=5xを解け. 2(3x+1)+(-(5x)) = 5x+(-(5x)) (2(3x)+2×1)+(-(5x)) = 0 ((2×3)x+2×1)+(-(5x)) = 0 (6x+2)+(-(5x)) = 0 (2+6x)+(-(5x)) = 0 2+(6x+(-(5x))) = 0 2+((1+5)x+(-(5x))) = 0 2+((1×x+5×x)+(-(5x))) = 0 2+(1×x+(5x+(-(5x)))) = 0 2+(x+0) = 0 2+x = 0 x = -2 5xの+の逆元-(5x)を足す. 分配律. xの結合律. 1を掛けても不変 +の交換律 +の結合律 分配律 +の結合律 1を掛けても不変,+の逆元を足すと0. 0を足しても不変

環 RじゃなくてR RingのR 集合R上の二項演算○と●が次をみたすとき, (R,○,●)は環であるという. ring 零元と呼ぶ zero (element) (1) (R,○)は群である.(結合律,単位元の存在,逆元の存在) commutative law (2)[○の交換律] すべてのa,b∈Rについて, a○b=b○a. associative law (3)[●の結合律] すべてのa,b,c∈Rについて(a●b)●c = a●(b●c). identity (element) (4)[●の単位元eの存在] e∈Rが存在して,すべてのa∈Rについてe●a=a, a●e=a. distributive law (5)[分配律] すべてのa,b,c∈Rについて a●(b○c)=(a●b)○(a●c), (a○b)●c=(a●c)○(b●c). 整数の+×を抽象化 しているので ●の逆元の存在は あえて外している 例 (Z,+,×), (Q,+,×), (R,+,×), (C,+,×)はいずれも環である.

環 例 整数n,aについて, nを法とするaの剰余類[a]をaで表すことにする. R:={0,1,...,n-1}上の演算+と×を次のように定めると(R,+,×)は環である. a+b = a+b, a×b = a×b (1) (R,+)は群.単位元(零元)は0. (2) a+b = a+b = b+a = b+a. (3) (a×b)×c = a×b×c = (axb)xc = ax(bxc) = ax bxc. (4) ×に関する単位元は1. (5) ax(b+c) = axb+c = ax(b+c) = (axb)+(axc) = axb+axc = (axb)+(axc). 例 n=6のとき + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 × 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1

体 体はドイツ語で Körper(ケルパ) 集合K上の二項演算○と●が次をみたすとき, (K,○,●)は体であるという. field (1) (K,○)は群である.(結合律,零元e0の存在,逆元の存在) 除算もできる!! (2) (K\{e0},●)は群である.(結合律,単位元e1の存在,逆元の存在) commutative law (3)[交換律] すべてのa,b∈Kについて, a○b=b○a. a●b=b●a. distributive law (4)[分配律] すべてのa,b,c∈Rについて a●(b○c)=(a●b)○(a●c), (a○b)●c=(a●c)○(b●c). 例 (Z,+,×)は体ではない.(×に関する2の逆元はZには無い) 例 (Q,+,×), (R,+,×), (C,+,×)はいずれも体である. ざっくり言うと体は加減乗除ができる代数系

体 例 整数n,aについて, nを法とするaの剰余類[a]をaで表すことにする. R:={0,1,...,n-1}上の演算+と×を次のように定めると nが素数ならば(R,+,×)は体である. a+b = a+b, a×b = a×b a×x = 1 (a≠0)をみたすxは, ax≡1 (mod n)の解x. nが素数ならgcd(a,n)=1だから解けて, aの逆元xが存在する. 例 n=5のとき. + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 × 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 0以外は逆元がある 例 n=6のときは体にならない. × 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1 2,3,4 は逆元を 持たない.

群と対称性

対称性 回転対称 点Oが存在して, 点Oを中心に回転しても 変わらない. 正三角形 線対称 直線lが存在して, 直線lを軸に反転しても 変わらない. △°中心点O σ120: 図形を時計回りに 120°回転する操作. σ240: 図形を時計回りに 240°回転する操作. σ0: 図形を時計回りに 0°回転する操作 (何もしないという操作) 3軸 l1,l2,l3 τ1: l1を軸に反転する操作. τ2: l2を軸に反転する操作. τ3: l3を軸に反転する操作. 正三角形には, σ120,σ240,σ0,τ1,τ2,τ3の6操作について対称性がある.

操作を元とする群 G:={σ0,σ120,σ240,τ1,τ2,τ3}とおく. Gに属する2つの操作x,yをx,yの順で行う連続操作を y○xで表す. ※対象aに操作fを施した結果をf(a)と表すと 操作f,gをこの順で行った結果はg(f(a)). 連続操作をg○fとしておけばg○f(a)=g(f(a)). 例 σ240○σ120 は120°回転してから240°回転する. よって, σ240○σ120 はσ0と同じ操作だから, σ240○σ120=σ0. 例 σ240○σ240 は480°回転だから120°回転と同じ. σ240○σ240=σ120. 例 τ1○τ2 は A B C → A C B → C B A だから120°回転と同じ. τ1○τ2=σ120. 例 σ120○τ3 は A C B → B C A → A B C だからl2反転と同じ. σ120○τ3=τ2.

操作を元とする群 G:={σ0,σ120,σ240,τ1,τ2,τ3} ○は, G上の二項演算である. 演算表 ○ σ0 σ120 σ240 τ1 τ2 τ3 σ0 σ0 σ120 σ240 τ1 τ2 τ3 σ120 σ120 σ240 σ0 τ3 τ1 τ2 σ240 σ240 σ0 σ120 τ2 τ3 τ1 τ1 τ1 τ2 τ3 σ0 σ120 σ240 τ2 τ2 τ3 τ1 σ240 σ0 σ120 τ3 τ3 τ1 τ2 σ120 σ240 σ0 (1) 結合律が成り立つ. 操作対象xに対して,(a○b)○cを施すと, c,b,aの順に操作が行われる (○と同じ結果になる) a○(b○c)を施しても c,b,aの順に操作が行われる (○と同じ結果になる) (2) σ0○x=x, x○σ0=x. (3) σ0○σ0=σ0, σ120○σ240=σ0, σ240○σ120=σ0. τ1○τ1=σ0, τ2○τ2=σ0, τ3○τ3=σ0. (G,○)は群である

対称性を群で捉える 問題. 赤玉と青玉をあわせて3個選んで円周上に等間隔に 置く置き方は何通りか? ただし,回転すると同じ配置になる置き方は区別しないものとする. 回転すると同じ配置になる置き方も区別すると2³=8通り. 2つの配置x,yが,回転対称性で同一視できるとき,x~yと表すと, ~は同値関係であり,その同値類の個数を求めればよい. よって,答えは4通り. 群を使って 書きたい.

対称性を群で捉える S:={ , , , , , , , } G:={σ0,σ120,σ240}, ○:連続操作 とおく. Gの元でSの元を操作するとSの元が得られる. よって, Gの元はSからSへの写像である. σ0,σ120,σ240はSからSへの全単射である. σ120 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ このような文脈では有限集合上の全単射は置換と呼ばれる. permutation

対称性を群で捉える S:={ , , , , , , , } G:={σ0,σ120,σ240}, ○:連続操作 とおく. (G,○)は群である. GはSの置換の集合だから permutation group (G,○)はSの置換群と呼ばれる. Sの2つの元x,yについて, Gの元aが存在してa(x)=y であることをx~yと表すと,~はS上の同値関係になる. その同値類の個数を求めればよい. →どうやって求める? よって,答えは4通り.

コーシー・フロベニウスの定理 定理(コーシー・フロベニウスの定理) バーンサイドの定理と呼ばれることもある. S:集合, G:有限集合, (G,○):Sの置換群. Sの置換g∈Gによって不変なSの元の集合をS^gで表す. S^g:={x|x∈S, g(x)=x} Sの2つの元x,yについて, Gの元aが存在してa(x)=y であることをx~yと表すと,~はS上の同値関係になる. その同値類の個数は, 1/|G| Σ|S^g| g∈G

対称性を群で捉える S:={ , , , , , , , } G:={σ0,σ120,σ240}, ○:連続操作 とおく. σ0 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ |S^σ0| = 8. σ120 不変 ↓ ↓ ↓ ↓ ↓ ↓ 不変 |S^σ120| = 2. σ240 不変 ↓ ↓ ↓ ↓ ↓ ↓ 不変 |S^σ240| = 2. よって, コーシー・フロベニウスの定理より 1/|G| Σ|S^g| = 1/3(8+2+2) g∈G = 4通り

ネックレス問題も同様に解ける 問題. 赤玉,青玉,緑玉をあわせて3個つないで作れる ネックレスは何通りか? ただし,回転や裏返しで 同じ配色となるネックレスは区別しないものとする. S:回転や裏返しで同じ配色となるものも区別した場合のネックレスの集合 G:={σ0,σ120,σ240,τ1,τ2,τ3}, ○:連続操作 とおくと, GはSの置換群である. |S^σ0| = |S| = 3³ = 27. 回転しても不変なネックレスは の3つ. ∴|S^σ120|=3, |S^σ240|=3. 直線lを軸とする裏返しで不変なネックレスは lの両側の玉が同色. ∴|S^τ1|=9, |S^τ2|=9, |S^τ3|=9. よって,答えは 1/|G| Σ|S^g| = 1/6(27+3+3+9+9+9) = 10通り. g∈G

ネックレス問題も同様に解ける S 1 2 3 2 4 5 3 5 6 2 4 5 4 7 8 5 8 9 3 5 6 5 8 9 6 9 10 Sは置換群Gで定義した同値関係によって 10個の同値類に分割される.

有限体上の幾何学

ゲームの対戦表のデザイン 3人対戦用ゲームがある. 9人の参加者がいる. どの人もできるだけ多くの人とバランス良く交流したい. 9人から3人を選ぶすべての組合せで対戦すれば, どの3人も1回ずつ交流でき,どの2人も7回ずつ交流できてバランスが良い. でも(9/3) = 84回も試合をするのは現実的でない. 試合数を減らしつつ,交流に偏りがないように 対戦表をデザイン(設計)しよう 例 どの2人も1回ずつ交流できる対戦表のデザイン. ラウンド1:{1,2,3},{4,5,6},{7,8,9} ラウンド2:{1,4,7},{2,5,8},{3,6,9} ラウンド3:{1,6,8},{2,4,9},{3,5,7} ラウンド4:{1,5,9},{2,6,7},{3,4,8} 日本語の「デザイン」は 見た目の創作を意味する. 英語の「デザイン」は 物事の設計を意味する.

組合せデザイン 何らかの制限の下での組合せの設計を研究する数学の分野を Combinatorial Design 組合せデザインと呼ぶ. v個の元からなる集合Vについて, Vの部分集合で,k個の元からなるものをブロックと呼ぶ. Vのブロックを元とする集合Bについて, Vのどの異なるt個の元も,Bのちょうどλ個のブロックで一緒に属するとき, design (V,B)をt-(v,k,λ)デザインと呼び,特にk≠vのとき 2-(v,k,λ)デザインをBIBD (balanced incomplete block design)と呼ぶ. 例 V={1,2,...,9} B={ {1,2,3},{4,5,6},{7,8,9}, {1,4,7},{2,5,8},{3,6,9}, {1,6,8},{2,4,9},{3,5,7}, {1,5,9},{2,6,7},{3,4,8} } 12ブロック→ (12試合) どの人も4試合する→ (V,B)は, 2-(9,3,1)デザイン ←どのた2人もちょうどλ=1試合で会う. 9人対戦ゲームで9人同時に遊べたらcompleteだけど そうでないときにもバランス良くデザインしたい.

平面と直線の抽象化 ユークリッド平面R² 異なる2つの直線は, 「共有点」を持たないとき「平行」である. (「直線」は自分自身とも「平行」である.) (1) 異なる2つの「点」を通る「直線」は唯一つ存在する. (2) 「直線」lと,lの上にない「点」pについて, pを通り,lと「平行」な「直線」が唯一つ存在する. (3) 「一直線上に並ばない」3つの「点」が存在する.

アフィン平面 (1)~(3)をみたす 「点」の集合Vと「直線」の集合Bの組 affine plane (V,B)をアフィン平面と呼ぶ. 例 V={a,b,c,d} B={{a,b},{a,c},{a,d}, {b,c},{b,d},{c,d}} 異なる2つの直線は, 「共有点」を持たないとき「平行」である. 共通部分がφ 例 {a,b}と{c,d}, {a,c}と{b,d}, {a,d}と{b,c}がそれぞれ「平行」. (V,B): (1) 異なる2つの「点」を通る「直線」は唯一つ存在する. 元として持つ 例 a,b∈Vを同時に元に持つBの元は{a,b}唯一つ. (2) 「直線」lと,lの上にない「点」pについて, 属さない pを通り,lと「平行」な「直線」が唯一つ存在する. 例 「直線」{a,b}∈Bと {a,b}に属さない「点」c∈Vについて, cを元として持ち,{a,b}との共通部分がφ であるBの元は{c,d}唯一つ. (3) 「一直線上に並ばない」3つの「点」が存在する. 1つの直線に属さない 例 a,b,cが属するBの元はない. 「直線」は抽象化され,長さ,形,位置などは捨象され 「まっすぐ無限に延びた線」という意味はもはや無い.

アフィン平面 (1)~(3)をみたす 「点」の集合Vと「直線」の集合Bの組 affine plane (V,B)をアフィン平面と呼ぶ. 例 V={1,2,...,9} B={ {1,2,3},{4,5,6},{7,8,9}, {1,4,7},{2,5,8},{3,6,9}, {1,6,8},{2,4,9},{3,5,7}, {1,5,9},{2,6,7},{3,4,8} } (V,B)はアフィン平面である. よって, "9人で3人対戦ゲーム"のBIBDを得た. 対応 (1)↔どの2人もちょうど1試合で会う. (2)↔各ラウンドでは誰もが試合できる. (3)↔incompleteである. アフィン平面をうまく構成できるとBIBDを得る!!

有限アフィン平面 体を使うとアフィン平面を構成できる. 体(K,+,×)のKがq個の元からなる有限集合のとき finite field Galois field (K,+,×)を有限体とかガロア体と呼び,FqとかGF(q)で表す. Fq=(K,+,×)について, V:={(x,y)|x,y∈K}=K². B:={{(x,y)|x,y∈K, ax+by=c}|a,b,c∈K, aとbのどちらかは零元でない} とおくと,(V,B)はアフィン平面である.(有限アフィン平面と呼ぶ.) Bの元{(x,y)|x,y∈K, ax+by=c}を直線ax+by=cと呼ぶ. おなじみの直線の式. この式をみたす点(x,y)の集合で直線を定義した.

有限アフィン平面 例 F2=(K,+,×)=({0,1},+,×) (2を法とする剰余類の集合上の体) V={(0,0),(0,1),(1,0),(1,1)} (x,y)を 座標だと思うと... 直線ax+by=cは全部で6本ある. (0,1) (1,1) (0,0) (1,0) ① 0x+1y=0 ③ 1x+0y=0 ⑤ 1x+1y=0 {(0,0),(1,0)} {(0,0),(0,1)} {(0,0),(1,1)} (0,1) (1,1) (0,1) (1,1) (0,1) (1,1) (0,0) (1,0) (0,0) (1,0) (0,0) (1,0) ② 0x+1y=1 ④ 1x+0y=1 ⑥ 1x+1y=1 {(0,1),(1,1)} {(1,0),(1,1)} {(0,1),(1,0)} (0,1) (1,1) (0,1) (1,1) (0,1) (1,1) (0,0) (1,0) (0,0) (1,0) (0,0) (1,0) ①と②, ③と④, ⑤と⑥が それぞれ平行. B={①,②,③, ④,⑤,⑥} (V,B)は 有限アフィン平面.

有限アフィン平面 例 F3=(K,+,×)=({0,1,2},+,×) (3を法とする剰余類の集合上の体) V={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)} (0,2) (1,2) (2,2) (0,1) (1,1) (2,1) (0,0) (1,0) (2,0) (x,y)を 座標だと思うと... 直線ax+by=cは全部で3³-3=24本ある? ① 0x+1y=0 ② 0x+1y=1 ③ 0x+1y=2 ① 0x+2y=0 {(0,0),(1,0),(2,0)} {(0,1),(1,1),(2,1)} {(0,2),(1,2),(2,2)} {(0,0),(1,0),(2,0)} ①と同じ 直線. ③ 0x+2y=1 ② 0x+2y=2 ④ 1x+0y=0 ⑤ 1x+0y=1 {(0,2),(1,2),(2,2)} {(0,1),(1,1),(2,1)} {(0,0),(0,1),(0,2)} {(1,0),(1,1),(1,2)}

有限アフィン平面 ⑥ 1x+0y=2 ⑦ 1x+1y=0 ⑧ 1x+1y=1 ⑨ 1x+1y=2 {(2,0),(2,1),(2,2)} {(0,0),(1,2),(2,1)} {(0,1),(1,0),(2,2)} {(0,2),(1,1),(2,0)} ⑩ 1x+2y=0 ⑪ 1x+2y=1 ⑫ 1x+2y=2 ④ 2x+0y=0 {(0,0),(1,1),(2,2)} {(0,2),(1,0),(2,1)} {(0,1),(1,2),(2,0)} {(0,0),(0,1),(0,2)} ⑥ 2x+0y=1 ⑤ 2x+0y=2 ⑩ 2x+1y=0 ⑫ 2x+1y=1 {(2,0),(2,1),(2,2)} {(1,0),(1,1),(1,2)} {(0,0),(1,1),(2,2)} {(0,1),(1,2),(2,0)}

有限アフィン平面 ⑪ 2x+1y=2 ⑦ 2x+2y=0 ⑨ 2x+2y=1 ⑧ 2x+2y=2 {(0,2),(1,0),(2,1)} {(0,0),(1,2),(2,1)} {(0,2),(1,1),(2,0)} {(0,1),(1,0),(2,2)} F3=(K,+,×)=({0,1,2},+,×) V={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)} 直線ax+by=cは全部で3³-3=24本ある? a=0,b=1のとき3本 a=1のとき3²=9本 ) 12本ある. B={...}

有限体上の幾何学を用いたゲーム対戦デザイン
q²人の参加者でq人対戦ゲームを遊びたい.
どの2人もちょうど1回ずつ交流できる対戦表をデザインする方法は?
有限体Fq=(K,+,×)が存在するなら
V:={(x,y)|x,y∈K}=K².
B:={{(x,y)|x,y∈K, ax+by=c}|a,b,c∈K, aとbのどちらかは零元でない}
とおくと(V,B)は有限アフィン平面である.
(V,B)の異なる2点を通る直線はちょうど1本で,どの直線もちょうどq点を通る.
よって,(V,B)は2-(q²,q,1)デザインであるから,
平行な直線は"同じ"とする同値関係でBを分割すれば,所望の対戦デザインを得る.
例 q=2のとき F2=(K,+,×), V=K²={①,②,③,④}とおく
③ ④
① ②
V
←平行
←平行
←平行
B
ラウンド1:{①,②},{③,④}
ラウンド2:{①,③},{②,④}
ラウンド3:{①,④},{②,③}

有限体上の幾何学を用いたゲーム対戦デザイン 例 q=3のとき, F3=(K,+,×), V=K²={①,②,③,④,⑤,⑥,⑦,⑧,⑨}とおく. ⑦ ⑧ ⑨ ④ ⑤ ⑥ ① ② ③ V {①,②,③} ラウンド1 {④,⑤,⑥} {⑦,⑧,⑨} {①,④,⑦} ラウンド2 {②,⑤,⑧} {③,⑥,⑨} {①,⑥,⑧} ラウンド3 {②,④,⑨} {③,⑤,⑦} {①,⑤,⑨} ラウンド4 {②,⑥,⑦} {③,④,⑧} B

各ラウンドの求め方 →簡単 →簡単 →1x+1y=cを解く→ →1x+2y=cを解く→ めんどくさい!!

各ラウンドの求め方 a,bが定まるとラウンドが定まり,ax+byの値をみれば(x,y)を通る直線がわかる. (平行な直線の組) 例 a=1, b=1のとき(ラウンド3のとき) x y 1x+1y 1x+1y=0 1x+1y=1 1x+1y=2 ① 0 0 0 ① ② 0 1 1 ② ③ 0 2 2 ③ ④ 1 0 1 ④ ⑤ 1 1 2 ⑤ ⑥ 1 2 0 ⑥ ⑦ 2 0 2 ⑦ ⑧ 2 1 0 ⑧ ⑨ 2 2 1 ⑨ ⑦ ⑧ ⑨ (0,2)(1,2)(2,2) ④ ⑤ ⑥ (0,1)(1,1)(2,1) ① ② ③ (0,0)(1,0)(2,0) 2 0 1 1 2 0 0 1 2

コンピュータのための離散数学入門, 離散構造入門, 基礎離散数学とその応用[第2版], 数学ガール ガロア理論, なっとくする 群・環・体, 数学30講 シリーズ 群論への30講, 基礎数学叢書12 情報数学入門, 東京大学工学教程 基礎数学 代数学, 数学のレッスン 計算体験を重視する入門, 代数学とは何か, 対称性からの群論入門, 代数学入門 先につながる群・環・体の入門, 群・環・体 入門, 共立講座 21世紀の数学9 代数と数論の基礎, 詳解 代数入門, 代数系入門, ABSTRACT ALGEBRA Second Edition

HANDBOOK OF COMBINATORIAL DESIGNS SECOND EDITION, COMBINATORIAL MATHEMATICS, Introductory Combinatorics, LATIN SQUARES AND THEIR APPLICATIONS, 基礎講座情報科学17 離散数学, COMBINATORICS: ANCIENT & MODERN, 組合せ論の発見, あたらしい情報数学, ガロアの数学入門, 現代代数学とその応用, 幾何学の魔術 魔方陣から現代数学へ, 組合せ数学入門I, 組合せ数学入門II, 現代数学序説, コンピュータのための離散数学入門, 離散構造入門, 基礎離散数学とその応用[第2版], 数学ガール ガロア理論