著者:徳田 雄洋[とくだ・たけひろ](1951-) 情報工学(言語処理系、情報ネットワーク、ソフトウェア生成系)。
イラスト:村山宇希[むらやま・うき]
シリーズ:ジュニア新書;751
NDC:410 数学
NDC:116 論理学.弁証法.方法論
件名:問題解決
備考:レベルは岩波ジュニア新書のなかでは高い部類に入る。記号・表記の面だけはすこし手加減してある。
うそつきか正直か不明な人から,質問1回で必要な情報を正確にもらう――そんな方法,知ってますか? この本で,論理的な解き方を身につければ,一見むずかしそうな問題もかんたんに解けるようになったり,新しい解決法を発見できたりします.数学や論理,情報科学はもちろん,日常おこる問題にも適用できますよ.
■内容紹介
5章に「重い偽コイン探し」という問題があります.
9枚のコインがある.8枚はほんもので同じ重さ,残り1枚はにせもので,ほんものより重いことがわかっている.上皿天秤を使って9枚のコインから1枚の偽コインを見つけたい.どのように計測をおこなえばいいか?
これは,まず,3枚ずつ3組(A,B,C)に分け,そのうちの2組を天秤の皿にのせて,計測することからはじまります.なぜ,3枚ずつ3組に分けるのか,については本を見ていただきたいのですが,AとBを皿にのせて計測したとき,もしAが重かったとしたら,Aのうちの1枚が偽コインになります.Bが重かったら,Bのうちの1枚が偽コインになります.つりあったら,Cのうちの1枚が偽コインになります.
すると,こんどは偽コインが入っているグループの3枚について,調べればいいことになります.これも天秤での計測1回で,どれが偽コインかがわかりますね.
この問題は,さらに発展します.27枚,81枚,243枚,….それぞれ何回の計測で偽コインを見つけられるか,もうおわかりですね.また,この章の「仕事は同じサイズに分割する」の意味もおわかりでしょう.3章で出る「嫉妬する夫問題」は時間順検討法という問題解決法で解け,「制限つき山くずし」は逆時間順検討法で解け,4章で出る「有名人問題」はまず理想の解があるものとして解けます.
各章でとりあげた問題が,その章のタイトルと確かに合致しているぞ,とわかれば,論理的に解く力が一部でも身についたことになります.そうなるよう,本書でとりあげた58問の解法の説明をじっくり読みこなしてください.暑い夏が少し涼しく過ごせるかもしれません.
【目次】
はじめに(2013年8月 徳田雄洋) [iii-v]
目次 [vii-ix]
論理的考え方にもとづく問題解決の12原則 [x]
第I部 基礎編
第1章 論理的に解くとは 001
問題1.1 手数料最小の会社合併
問題1.2 電話を2人でかけあう
問題1.3 偽コイン問題
問題1.4 ベランダ閉め出し
問題1.5 パスワード50個の管理
第2章 論理的考え方を利用する 009
場合分け法
問題2.1 3つの金属のかたまりの比較 014
不完全な場合分け
文の否定のつくり方
直接的推理法
逆と対偶
問題2.2 財布落とし主問題 020
2個以上の条件文の逆
問題2.3 3つの金属の判定表 023
問題2.4 偽コインの軽重判定 026
条件文の裏
問題2.5 不完全データベース問題 030
十分条件と必要条件
推論
背理法
問題2.6 白黒帽子問題 038
問題2.7 完全にそっくりな自宅の模型 040
問題2.8 部屋割り問題 042
問題2.9 教室の50人 043
問題2.10 2人の公平分割 044
数学的帰納法
問題2.11 素数は無限個ある 046
問題2.12 酔歩問題(ランダムウォーク) 049
問題2.13 分銅つくり 050
問題2.14 4桁符号配置 053
問題2.15 4人女王配置 056
第3章 問題解決法を利用する 059
時間順検討法
問題3.1 嫉妬する夫問題 60
逆時間順検討法
問題3.2 制限つき山くずし 63
問題3.3 かならずある不意試験 65
トップダウン法
問題3.4 到達問題 68
問題3.5 ベランダ閉め出し 69
問題3.6 パスワード50個の管理 70
問題3.7 5個の数字の和の最大値 72
第II部 詳細編
第4章 まず理想の解があるものとして 075
問題4.1 最年長者問題 77
問題4.2 有名人問題 79
問題4.3 ひっくりかえし整列問題 81
問題4.4 ひっくりかえしシャッフルゲーム
問題4.5 円盤問題 86
問題4.6 一般円盤問題 90
問題4.7 ケーキ公平分割 92
ナイフ移動法
最後に切った人法
逐次分割法
第5章 仕事は同じサイズに分割する 099
2分質問法
問題5.1 数当て問題 101
3分質問法
問題5.2 重い偽コイン探し 104
問題5.3 L字形タイル板問題 107
問題5.4 8つの数の最大と最小を見つける
問題5.5 8つの数の整列 113
問題5.6 27枚のコイン問題 115
原因設定法でコイン問題を解く
問題5.7 12枚のコイン問題 118
問題5.8 12枚、6枚、7枚、8枚のコイン問題 122
第6章 同じ仕事は1回だけ 129
問題6.1 5つの数の和の最大値 130
問題6.2 国境通過問題 134
問題6.3 クラブ所属問題 137
問題6.4 卵落下問題 139
第III部 応用編
第7章 目印をつくって分類する 145
問題7.1 階段ののぼり方 146
問題7.2 多角形の3角形分割 148
問題7.3 足し算の方法 151
問題7.4 最長共通部分列 153
問題7.5 最大上昇期間 156
第8章 場合分けして予測する 161
問題8.1 分かれている道 162
問題8.2 3人の公平分割 165
素朴法
1位2位同点法
問題8.3 2人で電話をかけあう 169
問題8.4 地震がおこるか、おこらないかの予言 171
問題8.5 1のカードか2のカードかの予言 172
問題8.6 偶数奇数の予言 174
第9章 可能なかぎりくりかえす 177
2つの整数の最大公約数
会社合併
問題9.1 5つの会社 180
最小和2社法
問題9.2 出発点へもどってくる道路 183
問題9.3 制限つき山くずし 186
問題9.4 分銅山くずし 189
問題9.5 8人の安定結婚 193
男子を申込者とする申込者優先法
問題9.6 不運な6人 196
参考文献 [199-201]
論理学/数学原論/組合せ数学とグラフ理論/情報工学/人間行動に関するゲームの理論/人間の心理学的ゲームの分類/組合せ論的ゲーム理論/ニムゲーム/偽コイン判定問題/公平分割/アルゴリズム集成
【メモランダム】
・自分用に、[問題一覧]を置いておく。
[問題一覧]
第I部 基礎編
第1章 論理的に解くとは 001
問題1.1 手数料最小の会社合併
問題1.2 電話を2人でかけあう
問題1.3 偽コイン問題
問題1.4 ベランダ閉め出し
問題1.5 パスワード50個の管理
第2章 論理的考え方を利用する 009
問題2.1 3つの金属のかたまりの比較 14
問題2.2 財布落とし主問題 20
問題2.3 3つの金属の判定表 23
問題2.4 偽コインの軽重判定 26
問題2.5 不完全データベース問題 30
問題2.6 白黒帽子問題 38
問題2.7 完全にそっくりな自宅の模型 40
問題2.8 部屋割り問題 42
問題2.9 教室の50人 43
問題2.10 2人の公平分割 44
問題2.11 素数は無限個ある 46
問題2.12 酔歩問題(ランダムウォーク) 49
問題2.13 分銅つくり 50
問題2.14 4桁符号配置 53
問題2.15 4人女王配置 56
第3章 問題解決法を利用する 059
問題3.1 嫉妬する夫問題 60
問題3.2 制限つき山くずし 63
問題3.3 かならずある不意試験 65
問題3.4 到達問題 68
問題3.5 ベランダ閉め出し 69
問題3.6 パスワード50個の管理 70
問題3.7 5個の数字の和の最大値 72
第II部 詳細編
第4章 まず理想の解があるものとして 075
問題4.1 最年長者問題 77
問題4.2 有名人問題 79
問題4.3 ひっくりかえし整列問題 81
問題4.4 ひっくりかえしシャッフルゲーム
問題4.5 円盤問題 86
問題4.6 一般円盤問題 90
問題4.7 ケーキ公平分割 92
第5章 仕事は同じサイズに分割する 099
問題5.1 数当て問題 101
問題5.2 重い偽コイン探し 104
問題5.3 L字形タイル板問題 107
問題5.4 8つの数の最大と最小を見つける
問題5.5 8つの数の整列 113
問題5.6 27枚のコイン問題 115
問題5.7 12枚のコイン問題 118
問題5.8 12枚、6枚、7枚、8枚のコイン問題 122
第6章 同じ仕事は1回だけ 129
問題6.1 5つの数の和の最大値 130
問題6.2 国境通過問題 134
問題6.3 クラブ所属問題 137
問題6.4 卵落下問題 139
第III部 応用編
第7章 目印をつくって分類する 145
問題7.1 階段ののぼり方 146
問題7.2 多角形の3角形分割 148
問題7.3 足し算の方法 151
問題7.4 最長共通部分列 153
問題7.5 最大上昇期間 156
第8章 場合分けして予測する 161
問題8.1 分かれている道 162
問題8.2 3人の公平分割 165
問題8.3 2人で電話をかけあう 169
問題8.4 地震がおこるか、おこらないかの予言 171
問題8.5 1のカードか2のカードかの予言 172
問題8.6 偶数奇数の予言 174
第9章 可能なかぎりくりかえす 177
問題9.1 5つの会社 180
問題9.2 出発点へもどってくる道路 183
問題9.3 制限つき山くずし 186
問題9.4 分銅山くずし 189
問題9.5 8人の安定結婚 193
問題9.6 不運な6人 196