4*4で最大いくつ置けるかって問題。数学オリンピックの過去問題にほぼ同じ問題があったので、正確に9個置ける証明を知りたい人のために。確か1974年のソ連の国内大会で、数オリ攻略本からのほぼパクリ回答です（p.164あたり）。
考え方は鳩ノ巣原理でOK
最大個数Mと配置出来たとする。
タテ4行のうち2行選んだとして、行を選ぶ総数は4C2=6行。
ある行の石の数をp_iとすると占拠する列の数は4Cp_i。
もちろん
Σ_i p_i=M
よって
Σ_i 4Cp_i <= 4C2
を満たすMを求めればOK
6 >= Σ_i (pi,2)
=Σ_i pi(pi-1)/2
12 >= Σ_i p_i(p_i-1)
=Σ_i (p_i^2-p_i)
=Σ_i (p_i^2)-M
>= (Σ_i pi)^2/4 -M (Mにしたいからコーシー・シュワルツの不等式。証明はてきとーな本みてください。）
=M^2/4-M
整理すると
M^2-4M-48 <=0
M <= 2*√13+2 ≒ 9.211
Mは整数なんで9個が最大。
間違いあったら報告お願いします。
