Java
アルゴリズム
数学
組み合わせ
数学パズル
More than 1 year has passed since last update.

こんな数学の問題見たことないでしょうか?

「この紙の上には、
1という数字が■個、2という数字が■個、
3という数字が■個、1から3まで以外の数字の
数が■個書いてある。 」

1枚の不思議な紙が落ちてました。
この紙には、この紙自身のことが書いてあります。
ところが、■に書いてあった4つの数字が消えていて読めません。
■に数字を入れて、この文が正しくなるようにしてください。

この答えは順番に4、1、3、1となります。実際に数字をあてはめて確かめて見てください
これは高校数学レベルの組み合わせの問題です。

このように自分から自分へ自己言及すると妙なことが起こります。

プログラム内で無限ループするかどうか判定するプログラムは存在しうるか?

という問題に通じることがあります。そのようなプログラムは存在し得ないわけです。
では次の問題はどうでしょう。

「この文章には1という数字が( )個含まれている」

( )に1を当てはめてみましょう。すると

「この文章には1という数字が(1)個含まれている」

となります。
文章中には合計で1が2回登場するので文章の意味と矛盾します。
( )にはいる数字は1ではないわけです

では9以下の1以外の整数を当てはめて見ましょう。

すると文章中には1は1回しか登場しないわけですが( )は1以外だったはずなので矛盾。つまり9以下の1以外の整数でもないわけです。

では10以上なのでしょうか?まさか。あり得ないでしょう。

つまり( )にはいる整数は存在しません。

数学的にあり得ないことが証明できました。はい、おしまい

答えは本当に存在しないのでしょうか?
いいえ存在します。それも無限に。

模範解答はこちら

\frac{1}{2}+\frac{3}{2}

上式には1が1つしか含まれていません。
したがって、文章中には合計で1が2回登場します。
また、上式を計算すると結果は2になります。

このように、実数同士の演算を行った結果が、式に登場する1の数と一致すれば良いわけです。

以下、イグザンプルです。

\lceil \sqrt{2} \rceil ,(6-5)
,\cos^2 49^ \circ +\sin^2 49^\circ, etc \cdots

確かに、なるほどといった感じです。
でも僕はあまり好きではありません
それはあくまで式であって数字ではないだろう、と思うからです。

日常生活で「りんごが$1/2+3/2$つあるね」
なんて言わないわけです。
式を数字として扱うのは計算機だけで十分です。

そこで思いついたのが整数の二進表記でした。
例えば0010bを文章中の( )に当てはめましょう。
文章中には合計で1が2回登場します。
また、10進表記で0010bは2を表すので矛盾なく文章を組み上げることができました。

二進表記では0と1だけで数を表すのでこの方法なら意味的に矛盾しない数を列挙することができるのでは?

そして、その整数列をオンライン整数辞典に載せたら人気出るかも…。

早速プログラムをかいてみました。3分くらいでかける簡単なプログラムです。

余談ですがJavaのInteger.bitCountの内部実装が面白いのでご紹介

public static int bitCount(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}

これだけでint の1のビットの数を数えることができてるんです。
ループや条件分岐などの制御構文を使わずにシフトと論理演算だけで
実装できるなんて…
ループを使わないので計算量は$O(1)$です。すごい
これはウェーブレット木という文字列探索アルゴリズムが元になっています。

さて、本題に戻ります。
プログラムを実行します。ウキウキと
./test.out 2000
なんて叩きます。
すると実行結果は

2
3

あれ?これだけ?
数字を増やしても結果は変わりません。
内部でもちゃんと動いてるようです。

そうです。
よく考えれば、整数の1のビットの数の増加率は少なくとも
$\log_2 n$以下に抑えられるから線形に増加する$n$に敵うわけないんです。

そんな当たり前のことに気づかなかった自分が恥ずかしいです

以下その証明

ある0以上の整数$n$について
$2^{i-1} \le n \le 2^i$
を満たすようなiが存在する。
この時$i$は、$n$を二進数表記する際に必要なビット数を表している

関数$B(n)$を次のように定義する

$B(n)$:={$n$を二進表記した時の1のビットの個数}

すなわち、
$B(n)+1=n$
を示せば良い
左辺は文章中に1が登場する合計を表している

定義から$B(n)$は
$0 \le B(n) \le i$
を満たす。
これから
$i-1 \le \log_2 n$
したがって

$0 \le B(n)=n-1 \le i \le 1+\log_2 n$
$0 \le n \le 2+\log_2 n$

等式が成立するのは$n=4$

これより、$0 \le n \le 4$が示せた。

よって等式を満たす整数は2,3のみ。

なんだか当たり前でしたね。

夜も眠れなくなるくらい面白いと思った問題でしたが実際は
驚きも何もない当たり前の結果。

なんだが凹んじゃいます。

教訓:寝る前に思いついたアイデアは大抵落とし穴がある。

以上。