数学クイズの傑作「破れたページの少女」を、Rubyで解いてみた

問題「破れたページの少女」
　　1枚だけページが破れた本がある。
　　破れていないページ番号を合計すると15000になる。
　　破れたページは何ページ目だろうか？
　　※元ソース…1994年のインド地方数学オリンピック

ある時SNSで見かけて知った数学の問題なのですが、なかなかスマートな問題ですよね。良い具合に引っ掛け要素があります。以下リンクでも詳しく解説されているので、こちらも御覧になってみてください。数学が好きな方は最初に是非解いてみてください^^

　　この問題についての詳しい解説はコチラ

この問題なのですが、以下の前提条件が無いと回答が難しくなるので、補足します。

　補足

・ 1ページからNページまで連続してページ番号が表示されており、ページNは奇数/偶数を問わない

・ 1ページ目の裏に2ページ目がある

「これ、合計が15000以外だとどんな解が得られるのかな」

… ふと思いたち、この問題をrubyで解けるようにしてみました。
(バージョン：ruby 2.5.1)

仕様

破れた本の、ページ番号の合計を入力(上記の問題通り実行する場合は15000を入力)すると
　　　　　　↓↓
この本の元々のページ数と、破られたページを求め、出力する

入力例

破かれた本の、ページ数を全て足した合計を入力してください。
合計は？ ：  ◯◯◯　←ここに入力

出力例

この本のページ数は、△△△ページです。
破かれたのは、□□ページ目です(同時に、◇◇ページ目も失われています)。

例外処理(解が得られなかった場合)

入力した合計値の条件では、解が存在しませんでした。

という結果が得られるように、コードを書いてみたいと思います。

考え方

前提として与えられているのは、破られた本の、ページ数を全て足した合計値のみ。元々の本の総ページ数も当然分からない状態です。なのでシンプルに、元々の本のページ数が１ページだとしたら → 2ページだとしたら → … という具合に、順に検証してみようかと思います。

以下が、コード内で用意した主な変数です。

• final_sum　…　最初に入力する合計値(問題文では15000)を入れる変数。
• book　…　本の本体。配列形式で、ページを１枚ずつ追加していきます。例)[1, 2, 3, 4, … ]
• pages_sum　…　破れていない場合の、bookのページ番号の合計値を入れる変数。
• torn_page_list　…　破くことが可能なページ全てのパターンを配列形式で追加していきます。 例)[[1, 2],[3, 4],[5, 6], … ]

例えば3ページ目を破ると、その裏の4ページ目も同時に失うことになります。そのためtorn_page_listには[x-1, x]というふうに格納していきます。且つ、[奇数, 偶数]の形でなければいけません。左右逆の[偶数, 奇数]だと、見開きページってことになってしまう(1枚だけ破くという前提が崩れてしまいNGとなる)為です。

bookにページを1枚ずつ追加していきながら…
本のページ番号合計 - 破いて無くなるページ合計 == 最初に入力した数値(問題文では15000)
つまり、
pages_sum - torn_page_list[？？].sum == final_sum
を満たすものを探し当てれば、ゴールです！

作成したコード(※まだ未完成)

sample.rb(コメント付き)

puts "破かれた本の、ページ数を全て足した合計を入力してください。"
print "合計は？ ："
final_sum = gets.to_i

# ↓ bookには、1ページずつ配列で格納していきます。 例) [1, 2, 3, .. ]
book = []

# ↓ pages_sumには、本のページ数を足していきます。
pages_sum = 0

# ↓ torn_page_listには、破ることが可能な全てのページを、パターンとして配列で格納していきます。 例) [[1, 2], [3,4], .. ]
torn_page_list = []

# ↓ インデックス値を用意
i = 1
# ↓ 以下のwhile文によって、条件を満たすケースが無いかを探り、無い場合はページを一枚ずつ追加し再検証する。
# ↓ なぜ final_sum + 1 なのかというと、「これ以上やっても、もう条件を満たすケースは無いよ！」というページ上限が、 final_sum + 1 の為。
while i <= final_sum + 1 do

  # ↓ 破るページを全ケース試して、解の条件を満たすケースが無いかを検証。
  lost_page_is = torn_page_list.find { |lost| pages_sum - lost.sum == final_sum }

  # ↓ 条件を満たすケースが見つかったら、while文をbreak(強制終了)する！
  break if lost_page_is != nil

  # ↓ 満たさなかった(上記でbreakしなかった)場合は、ページを増やし再検証する。
  book << i
  pages_sum += i
  if book.last.even?
    torn_page_list << [i - 1, i]
  end
  i += 1
end

# 結果を出力
if lost_page_is != nil
  puts "この本のページ数は、#{book.length}ページです。"
  puts "破かれたのは、#{lost_page_is[0]}ページ目です(同時に、#{lost_page_is[1]}ページ目も失われています)。"
else
  puts "入力した合計値の条件では、解が存在しませんでした。"
end

↓ コメントアウト無しバージョン ↓

sample.rb(コメントアウト無しバージョン)

puts "破かれた本の、ページ数を全て足した合計を入力してください。"
print "合計は？ ："
final_sum = gets.to_i

book = []
pages_sum = 0
torn_page_list = []

i = 1
while i <= final_sum + 1 do
  lost_page_is = torn_page_list.find { |lost| pages_sum - lost.sum == final_sum }
  break if lost_page_is != nil

  book << i
  pages_sum += i
  if book.last.even?
    torn_page_list << [i - 1, i]
  end
  i += 1
end

if lost_page_is != nil
  puts "この本のページ数は、#{book.length}ページです。"
  puts "破かれたのは、#{lost_page_is[0]}ページ目です(同時に、#{lost_page_is[1]}ページ目も失われています)。"
else
  puts "入力した合計値の条件では、解が存在しませんでした。"
end

結果

以下の通り、期待する結果を得ることが出来ました。

結果１

破かれた本の、ページ数を全て足した合計を入力してください。
合計は？ ： 15000
　　　　　　　　　　　　　↓
この本のページ数は、173ページです。
破かれたのは、25ページ目です(同時に、26ページ目も失われています)。

結果2

破かれた本の、ページ数を全て足した合計を入力してください。
合計は？ ： 3
　　　　　　　　　　　　　↓
この本のページ数は、3ページです。
破かれたのは、1ページ目です(同時に、2ページ目も失われています)。

結果3

破かれた本の、ページ数を全て足した合計を入力してください。
合計は？ ： 12345
　　　　　　　　　　　　　↓
入力した合計値の条件では、解が存在しませんでした。

このコードの課題①

上記で無事に解を得ることは出来たものの、解が存在しなかった場合の処理速度に課題を感じました。

アルゴリズムが持つべき性質…
有限性：アルゴリズムは終了しなければならない
明確性：アルゴリズムは実行する際の条件によって変動しないようにしなけらばならない
理解性：アルゴリズムはわかりやすいものでなければならない
高速性：アルゴリズムの処理は効率的でなければならない　←これ

上記が発生している理由は、while i <= final_sum + 1 do 〜 endの部分。あまりにも無駄な回数の繰り返し処理をさせていました。「これ以上繰り返しても無駄だよ」の境界値は、もっと厳密に定義しないといけません。

そこで考えたのが以下の表のイメージです。

本のページ数	破いた際の最小合計値(最後のページを破いた場合)	破いた際の最大合計値(１ページ目を破いた場合)
1ページ	-	-
2ページ	0	0
3ページ	1	3
4ページ	3	7
5ページ	6	12
nページ	book.sum-(book[n-1㌻]+book[n㌻])	book.sum-(book[0]+book[1])

"本を破いた際に得られる合計値"には、上記の通り得られる数値の範囲が決まっています(４ページある本なら、破いた後の合計値の取りうる範囲は、表の通り3〜7の間となる)。なので、その範囲を超えてまで、繰り返し処理をする必要は無さそうだ…ということが分かります。

課題①の改善方法

というわけで、while文の条件を以下のように書き換えようと思います。

sample.rb

# while i <= final_sum + 1 do 〜 end  ←これでは無駄に繰り返してしまうので、以下に変更
while pages_sum <= final_sum + (2 * i) - 1 do

上記のようにすると無駄な繰り返し処理がなくなり、例外処理も高速で処理出来るようになりました（元々がひどかっただけですがw）。

このコードの課題② 2020/5/15追記

以下の考察内容に、誤りがありました。　↓
別コードで検証してみた結果、どのような場合でも解は必ず１つのみになるようです。数学得意ではないので証明は出来ず…。
kts_h様から以下ご指摘をいただき、解が1つではない場合もあることが分かりました。教えていただき感謝です！

4855 のときには、99ページある本の47ページ目を破った場合だけでなく、100ページある本の97ページ目を破った場合でも成り立つので、答えは一つとは限らないようです。from @kts_h 様より…

課題②の改善方法

改善方法としては２つ。
①解が１つ見つかったとしても、breakでwhile分の繰り返しを止めずに、範囲内で解を探し続けること
②解が複数の場合を想定した変数管理に変え、出力内容も変更すること

課題①のほうの解決によって、余分な検索範囲が無い方法で処理できるようになるので、この2つの変更だけでスムーズに解決できそうです。

完成コード（2020/5/16更新）

sample.rb(完成バージョン)

puts "破かれた本の、ページ数を全て足した合計を入力してください。"
print "合計は？ ："
final_sum = gets.to_i

book = []
pages_sum = 0
torn_page_list = []

# 以下２つは、解が発見された場合に格納する為の変数
book_is = []
lost_page_is = []

i = 1
while pages_sum <= final_sum + (2 * i) - 1 do

  lost_page_is << torn_page_list.find { |lost| pages_sum - lost.sum == final_sum }
  unless lost_page_is.last == nil
    book_is << book.last
  end

  book << i
  pages_sum += i
  if book.last.even?
    torn_page_list << [i - 1, i]
  end
  i += 1
end

lost_page_is.compact!
unless lost_page_is == []
  lost_page_is.each_with_index do |lost, i|
    puts "#{book_is[i]}ページ分あった本の、#{lost[0]}〜#{lost[1]}ページ目が破かれています。"
  end
else
  puts "入力した合計値の条件では、解が存在しませんでした。"
end

この後ちゃんと検証してみた結果、解が２つ発生するケースは、1〜10000までの間では630件、10001〜20000までの間は645件もありました^^; そして、なんだかよく見ると不思議な法則性を持つ配列が出来上がりました(以下リスト参照)。

1〜10000までで、解が2つとなったリスト

4つ飛ばしのパターンが徐々に伸びていく不思議な配列が出来上がりました…
　 +4　/ +4 +4　/ +4 +4 +4　/ +4 +4 +4 +4　/ ...
3 21 25 55 59 63 105 109 113 117 171 175 179 183 187 253 257 261 265 269 273 351 355 359 363 367 371 375 465 469 473 477 481 485 489 493 595 599 603 607 611 615 619 623 627 741 745 749 753 757 761 765 769 773 777 903 907 911 915 919 923 927 931 935 939 943 1081 1085 1089 1093 1097 1101 1105 1109 1113 1117 1121 1125 1275 1279 1283 1287 1291 1295 1299 1303 1307 1311 1315 1319 1323 1485 1489 1493 1497 1501 1505 1509 1513 1517 1521 1525 1529 1533 1537 1711 1715 1719 1723 1727 1731 1735 1739 1743 1747 1751 1755 1759 1763 1767 1953 1957 1961 1965 1969 1973 1977 1981 1985 1989 1993 1997 2001 2005 2009 2013 2211 2215 2219 2223 2227 2231 2235 2239 2243 2247 2251 2255 2259 2263 2267 2271 2275 2485 2489 2493 2497 2501 2505 2509 2513 2517 2521 2525 2529 2533 2537 2541 2545 2549 2553 2775 2779 2783 2787 2791 2795 2799 2803 2807 2811 2815 2819 2823 2827 2831 2835 2839 2843 2847 3081 3085 3089 3093 3097 3101 3105 3109 3113 3117 3121 3125 3129 3133 3137 3141 3145 3149 3153 3157 3403 3407 3411 3415 3419 3423 3427 3431 3435 3439 3443 3447 3451 3455 3459 3463 3467 3471 3475 3479 3483 3741 3745 3749 3753 3757 3761 3765 3769 3773 3777 3781 3785 3789 3793 3797 3801 3805 3809 3813 3817 3821 3825 4095 4099 4103 4107 4111 4115 4119 4123 4127 4131 4135 4139 4143 4147 4151 4155 4159 4163 4167 4171 4175 4179 4183 4465 4469 4473 4477 4481 4485 4489 4493 4497 4501 4505 4509 4513 4517 4521 4525 4529 4533 4537 4541 4545 4549 4553 4557 4851 4855 4859 4863 4867 4871 4875 4879 4883 4887 4891 4895 4899 4903 4907 4911 4915 4919 4923 4927 4931 4935 4939 4943 4947 5253 5257 5261 5265 5269 5273 5277 5281 5285 5289 5293 5297 5301 5305 5309 5313 5317 5321 5325 5329 5333 5337 5341 5345 5349 5353 5671 5675 5679 5683 5687 5691 5695 5699 5703 5707 5711 5715 5719 5723 5727 5731 5735 5739 5743 5747 5751 5755 5759 5763 5767 5771 5775 6105 6109 6113 6117 6121 6125 6129 6133 6137 6141 6145 6149 6153 6157 6161 6165 6169 6173 6177 6181 6185 6189 6193 6197 6201 6205 6209 6213 6555 6559 6563 6567 6571 6575 6579 6583 6587 6591 6595 6599 6603 6607 6611 6615 6619 6623 6627 6631 6635 6639 6643 6647 6651 6655 6659 6663 6667 7021 7025 7029 7033 7037 7041 7045 7049 7053 7057 7061 7065 7069 7073 7077 7081 7085 7089 7093 7097 7101 7105 7109 7113 7117 7121 7125 7129 7133 7137 7503 7507 7511 7515 7519 7523 7527 7531 7535 7539 7543 7547 7551 7555 7559 7563 7567 7571 7575 7579 7583 7587 7591 7595 7599 7603 7607 7611 7615 7619 7623 8001 8005 8009 8013 8017 8021 8025 8029 8033 8037 8041 8045 8049 8053 8057 8061 8065 8069 8073 8077 8081 8085 8089 8093 8097 8101 8105 8109 8113 8117 8121 8125 8515 8519 8523 8527 8531 8535 8539 8543 8547 8551 8555 8559 8563 8567 8571 8575 8579 8583 8587 8591 8595 8599 8603 8607 8611 8615 8619 8623 8627 8631 8635 8639 8643 9045 9049 9053 9057 9061 9065 9069 9073 9077 9081 9085 9089 9093 9097 9101 9105 9109 9113 9117 9121 9125 9129 9133 9137 9141 9145 9149 9153 9157 9161 9165 9169 9173 9177 9591 9595 9599 9603 9607 9611 9615 9619 9623 9627 9631 9635 9639 9643 9647 9651 9655 9659 9663 9667 9671 9675 9679 9683 9687 9691 9695 9699 9703 9707 9711 9715 9719 9723 9727 計630件

複数解が得られるケースを探す、テスト用コード

def test(final_sum)
  book = []
  pages_sum = 0
  torn_page_list = []

  # 以下２つは、解が発見された場合に格納する為の変数
  book_is = []
  lost_page_is = []

  i = 1
  while pages_sum <= final_sum + (2 * i) - 1 do

    lost_page_is << torn_page_list.find { |lost| pages_sum - lost.sum == final_sum }
    unless lost_page_is.last == nil
      book_is << book.last
    end

    book << i
    pages_sum += i
    if book.last.even?
      torn_page_list << [i - 1, i]
    end
    i += 1
  end

  return lost_page_is.compact!.length

end

# 1から10000までの範囲で、複数解のケースがいくつあるかを出力
total = 0
(1..10000).each do |i|
  # 解が2つの場合を抽出
  if test(i) > 1
    total += 1
    print "#{i} "
  end
end
puts "◆ total: #{total}"

さらに念を入れ、解が3つのケースというのも検証した所、1から10万までの値の範囲では、ひとつも発見されませんでした。Macが熱々です。

というわけで、数字を扱う上での学びや、面白い発見の多い検証でした。ご覧いただきありがとうございました^^