本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(5)

プログラムといえばシミュレーション。今回のボールの問題はそれにピッタリ。ボールの増減の推移を追えば自ずと理屈が分かってくる

50. Last Ball

(a)20個の黒のボールと16個の白のボールが袋に入っている。その中からランダムに2個取り出し同色だったら白を1個入れ、異なる色だったら黒を1個入れる。この操作を残り1個になるまで繰り返す時、最後に残るボールは何か?

(b)20個の黒と15個の白で始めたらどうなるか?

結局白ボールが2ずつ減っていくということがわかれば(a)は白が1個になれないから最後に残るのは黒、(b)は白は0個になれないから自ずと最後に残るのは白とわかる。個人的にこういうパリティの問題好きです。数学の有名な証明が難しい定理も、mod 2の場合の証明は優しかったりしますからね

#50. LastBall
#(a) You have 20 black balls and 16 white balls in a bag.
#You repeat the following operation until a single ball is left in the bag.
#You remove two balls at a time. If they are of the same color,
#you add a black ball to the bag; if they are of different colors, you add a white ball to the bag.
#Can you predict the color of the last ball left in the bag?
#(b) Answer the same question if there are 20 black balls and 15 white balls to start with.

class Bag
    def initialize(bnum,wnum)
        @bnum=bnum
        @wnum=wnum
    end

    def remove
        r1=remove_one
        r2=remove_one
        add(r1==r2 ? :B : :W)
        [r1,r2]
    end

    def size
        @bnum+@wnum
    end

    def to_s
        "B:%d, W:%d"%[@bnum,@wnum]
    end

private
    def add(ball)
        if ball==:B
            @bnum+=1
        else
            @wnum+=1
        end
    end

    def remove_one
        if rand(size)<@bnum
            @bnum-=1
            return :B
        else
            @wnum-=1
            return :W
        end
    end
end

b=Bag.new(20,16)
puts b
until b.size==1
    b.remove
    puts b
end