こんにちは。今日で松の内も終わりです。

受験生の皆さんは年末年始もスペシャルゼミがあり、のんびりできなかったかもしれませんね。

 

さて皆さん、エルカミノからの年賀状問題は解けましたか？

今日は解答を発表しますので、答え合わせをしてみてください。

 

まずは問題のおさらいです。

5人がそれぞれの切手を集めています。切手は全部で31種類あります。

どの2人で見比べても、どちらも持っていない切手が△種類以上のとき、5人全員の切手を集めても絶対に31種類全部の切手はそろいません。

△に当てはまる一番小さい数字を求めなさい。

↓

↓

↓

【答え】19

【解説】

実際に試してみると表のように5人が切手を持っている場合、

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
A	○	○	○	○	○	○	○
Ｂ								○	○	○	○	○	○
C														○	○	○	○	○	○
D																				○	○	○	○	○	○
E																										○	○	○	○	○	○

Ａさんと他の4人はそれぞれ31－7－6＝18種類ずつ持っていない切手がありますが、5人合わせるとすべての切手が集まります。

よって△に当てはまる数字は19種類以上です。

 

では、本当に△が19のとき、5人の切手はすべてそろわないのでしょうか。

これを証明していきます。

 

まず、集めている5人を左に並べて、切手31枚を右に並べます。

そして次の作業をしていきます。

①　ある2人と切手を1枚ずつ見比べる

②　2人とも持っていない切手の場合、2人と切手をある色の線で結ぶ。どちらか1人でも持っていたら、線で結ばない

③　①と②を31枚すべての切手で行うが、②の作業は毎回異なる色で結ぶ

④　①～③を5人から2人を選ぶすべての組み合わせで行う。このときも、②の作業は今まで使っていない色で結ぶ

さて、何種類の色が必要になるでしょうか。

 

まず集めている人の立場で考えます。

5人から2人を選ぶ選び方は10通り。

そのそれぞれで19枚は持っていない切手がありますので、全部で19×10＝190種類以上の色を使うはずです。

一方、切手の立場で考えます。

もし、必ず誰か1人が持っているとすると、１枚の切手から出ている線の色は4人から2人を選ぶ6種類が最大です。

これが31枚ありますので，31×6＝186種類以下の色で線が結べます。

 

集めている人からは190種類以上の色の線を結ばなければならないのに、切手からは186種類以下の色しか結べません。

ということは「19種類持っていない切手がある」か「必ずだれか1人は持っている」というどちらかの条件が間違っていることになります。

よって19種類持っていない切手があることがわかれば、必ずだれも持っていない切手が存在することになります。

 

この「もし必ずだれか1人は持っているとすると……」と考える方法を背理法といいます。

また，問題の状況を線で結びながら考えていく方法をグラフ理論といいます。

どちらも数学で学習する内容ですが，小学生向けにアレンジして出題してみました。

今勉強している内容が、先々どのようになっていくか、少しでも感じてもらえるといいなと思っています。