[6章編]C++で「世界で闘うプログラミング力を鍛える本」をやっていく

この章について

タイトルとしては「数学と論理パズル」になっています。要は算数的(パズル的)問題や数学的問題が中心です。
まだ2章すら埋めきれてませんが息抜きに書くことにしました。(がんばりましょう)
場合の数や素因数分解あたりに関する常識は既知として扱います。

Question 6.1

20個の瓶にそれぞれ錠剤が入っています。そのうち19個の瓶には1.0グラムの錠剤が、残り1個の瓶には1.1グラムの錠剤が入っています。重さを正確にはかることのできるはかりが与えられたとき、どうやって重い錠剤の入った瓶を見つけますか？ただし、はかりは一度しか使うことができません。

(これ条件不足だろ)
普通のパズル問題となる程度に文章を解釈すると、
「はかりは一度しか使うことができません」 : 乗せた錠剤を1つ以上下ろした後に、もう一度、1つ以上の錠剤を乗せて重さを確認するのはダメ、つまり重さを確認できるのは一度のみ。

ということで、各瓶からどのように錠剤を取り出して組み合わせれば良いかを考える。
どの瓶にも十分な数の錠剤が入っているとすると、n番目(1≦n≦20)の瓶からn粒の錠剤を取り出して、これらの重さの合計を測る。このときm番目の瓶が該当の瓶であるとすると、重い錠剤は他の錠剤より0.1グラム重いので、錠剤は合計でm0.1 + 1.020*21/2 = 0.1m + 210グラムの重さになる。よって210グラムから何グラムはみ出しているかを確認すれば一目で判別可能となる。例えば、合計211.7グラムとなれば1.7グラムはみ出しているわけなので17番の瓶となる。

上の方法はn番の瓶にはn個以上の錠剤が入っている前提なので正直怪しいが...
解法から分かるように、個数順にソートした時にn番目の瓶にn個以上の錠剤が入っていれば大丈夫ではある。

Question 6.2

バスケットボールのゴールがあります。以下の2種類のゲームのうち、どちらか1つを選べるとします。
ゲーム1 : 1回だけ投げてシュートを決める
ゲーム2 : 3回投げてそのうち2回決める
1回投げてシュートを決める確率をpとすると、pの値がどのような場合に、どちらのゲームを選びますか？

素直に確率を計算するとよさそう。ゲーム2の「2回決める」は「2回以上決める」と解釈します。各々のゲームにおいて、勝てる確率を$ p_1 , p_2$とすると、
$ p_1 = p,$
$ p_2 =(3本とも決める確率) + (3本中2本ちょうど決める確率 ) = p^3 + 3p^2(1-p) = 3p^2 - 2p^3$
となるので、$ p_1 \ge p_2$ のときにゲーム1、そうでなければゲーム2を選択すれば良いことが分かる。
具体的に計算すると、
$ p_1 - p_2 = p - 3p^2 + 2p^3 = p(2p^2 - 3p + 1) = p(2p-1)(p-1)$
また、$ 0 \le p \le 1$ より $ p(p-1) \le 0 $ なので、$2p-1$の符号で完全に決定できる。
したがって、$0 \le p \le 1/2$ のとき $p_1 \ge p_2,$ $1/2 < p \le 1$ のとき $p_1 \le p_2$ を得る。
等号成立は $ p = 0, 1/2, 1$ のときで、ここの場合分けは好み。

Question 6.3

対角線上に2つの角が切り取られた、8×8のチェス盤があります。また、31個のドミノがあり、1つのドミノはちょうどチェス盤2マス分です。このとき、31個のドミノをチェス盤にすべて並べることができるでしょうか？できるとすればその例を、できない場合はその理由を述べてください。

有名問題。"チェス盤 敷き詰め 市松模様"とかでググると多分出ます。

Question 6.4

三角形のそれぞれ異なる頂点に3匹のアリがいます。アリが三角形の辺上を歩くとき、衝突する確率はどうなりますか？
それぞれのアリは進む方向をスタート時にランダムに選び、その確率は等しいものとします。また、歩くスピードはどのアリも同じとします。
同時に、n匹のアリが正n角形上を歩く場合についても衝突する確率を求めてください。

場合の数を数えましょう。最初から一般の場合について考えます。衝突しない場合、全員が右回りor左回りを選択したときなので2通り。一方で全てのアリの方向選択の場合の数は$2^n$通りなので求める確率は、余事象を考えて$1-\frac{2}{2^n}=1-\frac{1}{2^{n-1}}$

Question 6.5

5クォート、3クォートの水が入る壺がそれぞれ1つずつあります。また、十分な量の(しかし量を量ることはできない)水があります。このとき、ちょうど4クォートの水を量るにはどのようにすればよいですか？ただし壺は変わった形をしており、ちょうど半分水を入れるというようなことはできません。

これもよく見かける。5と3から4を作るのは見飽きたので問題文を、

"$a$クォート、$b$クォートの水が入る壺がそれぞれ1つずつあります。また、十分な量の(しかし量を量ることはできない)水があります。このとき、ちょうど$n$クォートの水を量るにはどのようにすればよいですか？ただし壺は変わった形をしており、ちょうど半分水を入れるというようなことはできません。"

と書き換えます。なのでこの場合は$n$クォートぴったり量れない場合もあるかもしれないので、それも含めて考察します。
勘の鋭い方はお気づきかと思いますが、$gcd(a,b)$ | $n$の場合のみ構成できて、逆に、これ以外の場合は構成不可能であることが示せます。
あと今回の制約から、$n \le max(a,b)$と仮定しておきます。

(証明)
$a \le b$として一般性を失わない。まず$g=gcd(a,b)|n$と仮定する。このとき、ディオファントス方程式$ax+by=g$は整数解$(x,y)$を持つ。特に、$ax+by=n$も整数解$(x,y)$を持つことになる。
このとき、$ax+by≡ax≡n(mod$ $b)$が成立する。また、$(x,y)$が$ax+by=n$の解であるとき、$(x-bt,y+at),(t∈\mathbb{Z})$も解になることから、$0 \le x < b$となるように$x$を取りなおすことができる。
よって、"$a$クォートの壺をいっぱいにして、その水を$b$クォートの壺に注ぎ、満杯になればその都度$b$クォートの壺を空にする"という操作を$x$回行うことによって、制約の下で構成可能であることが示された。($b$クォートの壺に$n$クォートの水が満たされた状態になる。)
逆に、$gcd(a,b)$が$n$を割らないと仮定する。このとき、ディオファントス方程式$ax+by=n$が解を持たないことから、これは構成不可能である。
以上より示された。

構成可能な場合の構成例を与えるコードを以下に示しておきます。

6-5.cpp

#include<iostream>
using namespace std;
int gcd(int a,int b){
    if(a>b){swap(a,b);}
    if(a==0){return b;}
    else{return gcd(b%a,a);}
}

void status(int a,int b){
    cout<<"aクォートの壺の水量 :"<<a<<' '<<"bクォートの壺の水量 :"<<b<<endl;
}

void water(int a,int b,int n){
    if(a>b){swap(a,b);}
    if(n>b||(b%gcd(a,b)!=0)){cout<<-1<<endl;}//構成不可能な場合は-1を出力することにした
    //それ以外は構成可能なので以下処理
    int A = 0,B = 0;
    while(B!=n){
        status(A,B);
        B += A;
        if(B > b){
            A = B - b; B = b;
            status(A,B);
            B = 0;
            }
        else{
            if(B > 0){status(0,B);}
            A = a;
            }
    }
}

出力例($a=3,b=5,n=4$)

aクォートの壺の水量 :0 bクォートの壺の水量 :0
aクォートの壺の水量 :3 bクォートの壺の水量 :0
aクォートの壺の水量 :0 bクォートの壺の水量 :3
aクォートの壺の水量 :3 bクォートの壺の水量 :3
aクォートの壺の水量 :1 bクォートの壺の水量 :5
aクォートの壺の水量 :1 bクォートの壺の水量 :0
aクォートの壺の水量 :0 bクォートの壺の水量 :1
aクォートの壺の水量 :3 bクォートの壺の水量 :1
aクォートの壺の水量 :0 bクォートの壺の水量 :4

Question 6.6

ある島に、さまざまな眼の色をした人たちが仲良く暮らしていました。しかし、ある日突然島の外から人がやってきておかしなことを言います。「青い眼をした人は、できるだけ早くこの島から出ていきなさい」。毎晩午後8時に島から飛び立つ飛行機が出ていて、自分自身の眼の色が青色だとわかった時点で、その人は飛行機に乗って島を出なければなりません。島の人たちは自分以外の人の眼の色がわかりますが、自分の眼の色はわかりません。また、自分の眼の色を他人に聞いたり、他人に眼の色を教えてあげるということは禁止されています。また、島全体で青い眼をした人が何人いるかはわかりません。
ただし、少なくとも1人はいることがわかっています。青い眼をした人が島からいなくなるには何日かかるでしょうか？

一旦、飛行機には任意の人数が乗れるものとして議論します。
結論から述べると、島にいる青い眼をした人の人数を$M$人とすると、$M$日目に彼ら全員が島から去ります。

前提として彼らは島から出て行きたくないので、普通の眼の色の人たちは、自分が視認できる$M$人のみが青い眼だと思っていて(実際その通りなわけだが、青い眼の人たちが去るまではわからない)、青い眼の人たちは自分以外の$M-1$人が青い眼をしていると思っている。

せっかくなので帰納法で示す。
・$M=1$のとき
青い眼をした人が一人だけいて、その人から見ると自分以外の誰も青い眼をしていないので自分が青い眼であることに気付く。(島には青い眼をした人が少なくとも1人いるということを彼らは知っているので)
よってこの人が1日目に島から出て行くので成立。

・$M=k-1(k \ge 2)$のときに成立すると仮定する。つまり、$k-1$日目に全員島から出て行くとする。
このとき、$M=k$のとき、$k$日目に青い眼をした人全員が島からいなくなることを示す。
青い眼をした人を適当に1人選ぶ。このとき、この人は自分以外の$k-1$人が青い眼をしているように見えるわけなので、仮定より$k-1$日目に彼らが飛行機に乗って島から出て行くと思い込んでいる。しかし、青い眼をした他の人々も同じことを考えているので、$k-1$日目の飛行機には乗らない。
このとき、$k$人全員が自分も青い眼であることに気付くので、彼らが$k$日目の飛行機に乗って島を出て行くことになる。よって示された。

要は飛行機のキャパシティに関係なく$M$日目に$M$人全員が自分の眼が青いことに気付くので、キャパシティが有限(一度に$N$人まで)としても、$[(M-1)/N]$日ほど日数が増えるだけとなる。

Question 6.7

現在の文明が滅んだあとの新しい世界で、女王は出生率について心の底から心配していました。そのため女王は、すべての家族は1人女の子を持つか、そうでなければ多額の罰金を支払わねばならないという法令を作りました。すべての家族がこの規則を守るとすると (つまり女の子が生まれるまで子を持ち続け、生まれた時点で子供を増やすのをやめると)新しい世代の男女比はどのようになるでしょうか？(生まれる子どもが男である確率も女である確率も同じであると仮定してください。)この問題について論理的に解答し、そのあとコンピュータシミュレーションを行ってください。

1家庭から生まれる子どもの人数の期待値$E$を考えます。$k-1$人目まで男で、$k$人目にようやく女が生まれる確率を$p_k$とすると、男女どちらも生まれる確率は等しく$1/2$であることから
$p_k = (k-1人連続男が生まれる確率)×(女が生まれる確率) = \frac{1}{2^{k-1}} × \frac{1}{2} = \frac{1}{2^k}$
よって求める期待値は、
$E = \sum_{k=1}^{\infty}kp_k = \sum_{k=1}^{\infty}\frac{k}{2^k} $
この値はシミュレーションすることで(例えば以下)、おそらく2に収束する、つまり男女比は1:1になるだろうと予想されます。入力の$n$の値を大きくすれば精度が上昇するのでコンピューターによる考察はここまでだと分かります。

6-7.cpp

#include<iostream>
#include<cmath>
using namespace std;

double frac(double k){
    double bunsi = k;
    double bunbo = pow(2,k);
    return (bunsi/bunbo);
}

int main(){
    int n;
    cin>>n;//無限級数のn項目までの部分和を考える
    double ret=0;
    for(int i=1;i<=n;i++){
        ret+=frac(i);
    }
    cout<<ret<<endl;
    return 0;
}

実際に$E$が2に収束することを示す。
準備として、関数 $f(x)=\frac{1}{1-x}$を考える。この関数を形式的冪級数で表示すると、
$f(x)=\sum_{i=0}^{\infty}x^i$
で、これは $|x|<1$で収束する。
いま、$f(x)=\frac{1}{1-x}$ でもあったので、先ほどの級数と等号で結んで両辺を微分すると、
$\sum_{i=1}^{\infty}ix^{i-1} = \frac{1}{(1-x)^2}$
(右辺の定数項は消えるので、$i=1$から和が始まる)
両辺に$x$をかけて、
$\sum_{i=1}^{\infty}ix^i = \frac{x}{(1-x)^2}$
これらは収束半径内での極限が存在し、$x \rightarrow \frac{1}{2}$ とすることで両辺2に収束する。
したがって、$E=2$となるのでやはり男女比は$1:1$に収束することがわかる。

Question 6.8

100階建ての建物があります。$N$階以上の高さから卵を落とすと卵は割れてしまいます。$N$階より下からであれば卵は割れません。2つの卵を使い、落とす回数をできるだけ少なくなるように$N$を見つけてください。

卵が2個しかなくて二部探索できないので工夫が必要。方針としては、1つの卵は実験用に使ってもう1つの卵で細かく探っていく。この探り方の最適解を考える。

最初に僕の間違えた(?)答案を書きます。想定解だけ知りたい人は次の赤文字までスクロールダウンしてください
下から数えて$N$階ではじめて卵が割れるとして、一つの方法$W$に対してかかる操作回数を$W(N)$とする。このとき、操作回数の期待値$E(100W)=\sum_{N=1}^{100}W(N)$ を最小にする$W$が理想的な方法であると言える(と思った)。

つまり、1つの卵が壊れるまで$M$階刻みで上がっていって、1つ目の卵が壊れたら壊れた階の$M$階下からもうひとつの卵が壊れるまで1階ずつ刻んでいく。この$M$として最適な値を考える。
$M \le 100$だしシミュレーションしても良いがこれもせっかくなので計算する。
上記の方法を$W$とすると、
$W(N)=\lceil{\frac{N}{M}}\rceil + R(N)$ (ただし、$R(N)$は$N$を$M$で割ったときのあまり,$\lceil{x}\rceil$は$x$以上の最小の整数)
これを$N=1$から$N=100$まで加える。割り算をすることで整数$q,r$を用いて$100=Mq+r(0 \le r <M)$と書けるので、
$E(100W)=\sum_{N=1}^{100}W(N)=\sum_{N=1}^{Mq+r}W(N)=(\sum_{N=1}^{Mq}+\sum_{N=Mq+1}^{Mq+r})W(N)$
$(右辺第一項)=\sum_{i=0}^{q-1}\sum_{j=1}^{M}W(Mi+j)=\sum_{i=0}^{q-1}\sum_{j=1}^{M}(i+1+R(j))=\sum_{i=0}^{q-1}(M(i+1)+\frac{M(M-1)}{2})$
$=M\frac{q(q+1)}{2}+q\frac{M(M-1)}{2}=\frac{Mq(M+q)}{2}$
$(右辺第二項)=\sum_{N=Mq+1}^{Mq+r}W(N)=\sum_{N=Mq+1}^{Mq+r}(q+1+R(N))=r(q+1)+\frac{r(r+1)}{2}$
したがって、
$\sum_{N=1}^{100}W(N)=\frac{Mq(M+q)}{2}+r(q+1)+\frac{r(r+1)}{2}$
また、$r=100-Mq$ だったのでこれを代入すると、
$\frac{Mq(M+q)}{2}+(q+1)(100-Mq)+\frac{(101-Mq)(100-Mq)}{2}$
ここで、$q=\lfloor\frac{100}{M}\rfloor$なので、このままだと場合分けが大変。先に$M$ | $100$の場合を計算する。このとき、$Mq=100$より$q=\frac{100}{M}$となるので、
$E(100W)=\frac{100(M+\frac{100}{M})}{2}=50(M+\frac{100}{M})$
相加・相乗平均の不等式より
$M+\frac{100}{M} \ge 2\sqrt{M\frac{100}{M}}=20$
なので、
$E(100W) \ge 50*20=1000,$等号成立は$M=\frac{100}{M}$すなわち$M=10$のとき。
よってこの場合は$M=10$で最小値1000を与える。

次に$M$が100を割らない場合を考察したかったが、上手い不等式評価が思いつかなかったので諦めてコードを書いてしまった。以下の結果より$M=11$のときに$E(100W)=1001$となりこの場合はこれが最小。

6-8.cpp

#include<iostream>
#include<cmath>
using namespace std;

int ExpectedValue(int m){
    int q = 100/m;
    int ret =m*q*(m+q)/2+(q+1)*(100-m*q)+(101-m*q)*(100-m*q)/2;
    return ret;
}

int main(){
    int minExp=1000000;
    int m;
    for(int M = 1;M < 101;M++){
        if(100%M!=0){
            if(minExp > ExpectedValue(M)){
                minExp = ExpectedValue(M);
                m = M;
            }
        }
    }
    cout<<minExp<<endl;
    cout<<m<<endl;
}

以上より、卵を落とす高さを10階ずつ上げていくのが最適解だと思った。

~本にあった最適解~
そもそも"最適な方法"に対する見方が違った。自分は卵を落とす回数の期待値を最小化していたが、想定解では"最悪ケースでの操作回数"を最小化していた。
そのような思想の下では、最適な方法なら2つの卵を落とした回数の合計が一定値になるはずである。
つまり、上の階に進むにつれ1つ目の卵を落とす回数は1回ずつ増え、それに伴い2つ目の卵を落とす回数は1回ずつ少なくならないといけないので、最初に$X$階の高さから卵を落とすとき、次は$X-1$階上から落とさないといけない。その先も$X-2,X-3$階...と細かくしていく。そうして今いるフロアの1階上から1つ目の卵を落とす頃に100階に到達しないといけないので、$X+(X-1)+...+2+1=\frac{X(X+1)}{2}=100$
となるはずである。このとき、
$X=\frac{-1\pm3\sqrt{89}}{2}$
となり、正の解を採用して$X\approx13.6$ ということになる。
よって$X=13or14$とすべきだが、最悪ケースを実験してみることで$X=14$が最適解を与えることが分かる。
このとき、最悪ケースでも卵を落とす回数の合計は14回になる(試すとわかる)。

Question 6.9

廊下に扉のしまったロッカーが100個あります。まず、100のロッカーの全ての扉を開けます。次に、2つごとに(1つ飛びで)扉を閉めていきます。今度は3つごとに(2つ飛びで)扉が空いていれば閉めて、閉まっていれば開けていきます。このようなことを繰り返していくと、100回目に100番目のロッカーの開け閉めをして終わります。その時点で、開いている扉はいくつありますか？

$k$番目の操作で$k$の倍数の番号のロッカーの状態を変化させるということなので、$n$番ロッカーの最終的な状態は$n$の約数の個数に依存する。特に、$n$の約数が奇数個であるとき、ロッカーは最終的に開いている状態となる。
$n$の素因数分解を
$n=\prod_{i=1}^{m}p_i^{q_i}$ とすると、その約数の個数$\phi(n)$ は $\phi(n)=\prod_{i=1}^{m}(q_i+1)$ で与えられる。$\phi(n)$が奇数となるとき、すべての$i$について$q_i$が偶数となることが必要十分条件である。これは$n$のすべての素因数が偶数であることを指しているので、言い換えるとこのような$n$は平方数ということになる。1以上100以下の平方数は$1^2$から$10^2$までの10個なので、答えは10個。

Question 6.10

ソーダのボトルが1000本あり、1本だけ毒が入っています。また、毒を検知する試験紙が10枚あります。1滴の毒で試験紙は恒久的に陽性を示します。試験紙には一度に何滴でも投下することができ、試験紙は(陰性の結果である限りは)何度でも好きなだけ再利用できます。しかし1日に1回しかテストはできず、結果がわかるには7日かかります。できるだけ少ない日数で毒の入ったボトルを特定するにはどのようにすればよいでしょうか？

10と1000という数を見てピンときた人は答えがすぐ分かったと思います。結論を述べると1回の検査(つまり7日)で毒の入ったボトルを特定することができます。

各試験紙とボトルについて、そのボトルのソーダが"投下されている"か"投下されていない"の2種類の状態のどちらかになっています。つまり、1つのボトルに対して10枚それぞれの試験紙に投下するかしないかを選択できるので、その場合の数は$2^{10}=1024$通りとなります。
ではこれをどう使えば1回の検査で済むかを説明します。
各$n(1 \le n \le 1000)$に対して2進数表示を考えます。$1000 < 1024=2^{10}$なのですべての$n$を10桁以内の2進数で表示できます。このとき、ビットが立っている部分(=2進数表示で1となっている部分)に対応する番号の試験紙にのみ$n$番のボトルの中身を投下します。

例えば$n=691$としたとき、これの2進数表示は1010110011となります。なのでこの場合は左から数えて1,3,5,6,9,10番目のビットが立っているので、この順番に対応する試験紙だけに691番ボトルの中身を投下します。
このようにして、これを$n=1$から$n=1000$まで同じ操作を行います。つまり、どの試験紙にも複数のボトルの中身が投下された状態です。

こうすることで7日目に1枚以上の試験紙が陽性を示すわけですが、ボトルに対する試験紙の選び方から、陽性を示した紙を1,陰性を示した紙を0として2進数として繋げて読むことで、そのまま毒入りソーダの入ったボトルの番号が分かります。