4. クラス編成問題
各生徒の志望順位
第一志望 第二志望 第三志望
→
←
低
高
成
績
生徒a
クラスA
クラスB
クラスC
生徒b
クラスA
クラスB
クラスC
生徒c
クラスA
クラスB
クラスC
生徒d
クラスB
クラスA
クラスC
生徒e
クラスA
クラスC
クラスB
生徒f
クラスB
クラスA
クラスC
*1クラス定員2名で6名の
生徒を3つのクラスに振り
分けたい
どのように振り
分けたら良い
か?
クラス分けの方法 1

成績の良い人から順にクラスを決定
(表を横に見ていく)
第一
志望
第二
志望
第三
志望
生徒a
A
B
C
生徒b
A
B
C
生徒c
A
B
C
生徒d
B
A
C
生徒e
A
C
B
生徒f
B
A
C
<<性質>>
「自分が行きたくても行けな
かったクラスに入っている
生徒は、皆自分より成績が
良い」
公理論的アプローチ(方法1)
公理・・・証明なしで認めるもの
定理・・・公理から導かれるもの
方法1の公理
「自分が行きたくても行けなかったクラスに入っている
生徒は、皆自分より成績が良い」
必要十分
成績の良い順にクラスを決めていく方法で
求めたクラス分け
証明
・成績1番の生徒 →第1志望
・成績2番の生徒 →1番の学生で第1志望が →第2志望へ
埋まっている
→ 埋まっていない
第一
志望
第二
志望
第三
志望
生徒a
A
B
C
生徒b
A
B
C
生徒c
A
B
C
生徒d
B
A
C
生徒e
A
C
B
生徒f
B
A
C
帰納法
→第1志望へ
クラス分けの方法 2

志望順位でクラスを決定
(表を縦に見ていく)
第一
志望
第二
志望
第三
志望
生徒a
A
B
C
生徒b
A
B
C
生徒c
A
B
C
生徒d
B
A
C
生徒e
A
C
B
生徒f
B
A
C
* 定員一杯だったクラスを志望して
いる生徒については、クラスを割り当
てずに保留
<<性質>>
「自分が行きたくても行けなかった
クラスに入っている生徒は、
そのクラスの志望順位が自分より高
かったか、志望順位は自分と同じだけ
ど成績が自分より良かった」
公理論的アプローチ(方法2)
方法2の公理
「自分が行きたくても行けなかったクラスに入ってい
る生徒は、そのクラスの志望順位が自分より高かっ
たか、志望順位は自分と同じだけど成績が自分より
良かった」
必要十分
志望順位でクラスを決定する
方法で求めたクラス分け
証明
背理法
方法2とは別の、公理を満たすクラス分けがあると仮定
<方法2のクラス分け>
あるクラス
志望順位
<2位>
<別のクラス分け>
あるクラス
志望順位
<3位>
×
×
2位
3位
矛盾が生じる
戦略的操作性
方法2のクラス分け
生徒Cの志望順位変更後
第一
志望
第二
志望
第三
志望
第一
志望
第二
志望
第三
志望
生徒a
A
B
C
生徒a
A
B
C
生徒b
A
B
C
生徒b
A
B
C
生徒c
A
B
C
生徒c
B
A
C
生徒d
B
A
C
生徒d
B
A
C
生徒e
A
C
B
生徒e
A
C
B
生徒f
B
A
C
生徒f
B
A
C
戦略的操作性がある
ダウンロード

4. クラス編成問題