FC2ブログ

Welcome to my blog

[答992] 1000以下の自然数

ヤドカリ

ヤドカリ



[答992] 1000以下の自然数


 1000×1000 のマス目があって、どの行も左のマス目から順に どの列も上のマス目から順に、

 1000以下の自然数のうち、記入するマス目と 同じ行の左のマス目と同じ列の上のマス目に

 記入されてる自然数以外の、最大のものを記入します。

 ただし、そのような 1000以下の自然数がないときは「×」を記入します。

 例えば、黄色で示した「997」はその上や左の赤の数以外の、1000以下の最大の自然数です。

 このようにして全部のマス目に 1000以下の自然数または「×」が記入された状態で、

 (1) 「992」が書かれているマス目は何個?  (2) 「×」が書かれているマス目は何個?


[準備]

 まず、使用する文字は 負でない整数とします。

 1000以下の自然数のうち最大のもののかわりに、負でない整数のうち最小のものを記入すれば、

 下の表のようになり、上下の表で対応するマス目の数の和は 1000になります。

 ただし、下の表で 1000以上の数のマス目に対応する上の表のマス目は「×」です。

 下の表では、例えば 赤で示した「5」と同じ行の一番左が「3」で同じ列の一番上が「6」ですが、

 2進法では 3=011(2) ,6=110(2) ,5=101(2) ですので、

 3 と 6 の2進法で桁毎の排他的論理和( V )が 5 になります。 3 V 6=5 です。

 排他的論理和とは、0 V 0=1 V 1=0 ,0 V 1=1 V 0=1 とする演算で、

 整数 x,y,z について x V y=y V x ,x V y=z のとき x V z=y が成り立ちます。

 ( x V y を x ^ y ,x xor y ,bitxor(x,y) と表すこともあります )

 また、下の表では一般に、

 表に書かれた各数を X,同じ列の一番上の数を T,同じ行の一番左の数を L とすれば T V L=X ……(*)

 が成り立ちます。

 まず、表のすべての数において、(*)が成り立つことを示します。

 例えば、黄色で示した左上の 4×4 の部分で成り立つ事を確かめておけば、

 その右や下の水色で示した 4×4 の部分は 黄色の各数に 4=100(2) を加えたもので、

 その右下のピンクで示した 4×4 の部分は 黄色の各数と同じですので、

 8×8 の部分でやはり(*)が成り立ちます。

 同様に、(*)が、左上の 2n×2n で成り立てば、 2n+1×2n+1 で成り立ちます。

 こうして、表のすべての数について(*)が成り立ちます。


[解答]

 999=1111100111(2),1000=1111101000(2) です。

(1) 上の表で「992」が書かれているマス目の個数について、

 対応する下の表のマス目には「8」が書かれていますので、

 x≦999,y≦999,x V y=8 を満たす(x,y)の組数を求めることになります。

 x V y=8 より x V 8=y 、x V 8≦999 、

 x V 1000(2)≦1111100111(2) です。

 1111100000(2)≦x≦1111100111(2) だけが適さないので、1000-8=992 個です。

(2) 上の表で「×」が書かれているマス目の個数について、

 対応する下の表のマス目には 1000以上の数が書かれていますので、

 x≦999,y≦999,x V y>999 を満たす(x,y)の組数を求めることになります。

 x V y=z とすれば x V z=y になり、

 x,y は2進法で 10桁以下なので、z≦210-1=1023 だから、

 x≦999,1000≦z≦1023,x V z≦999 を満たす(x,z)の組数を求めます。

 1111101000(2)≦z≦1111111111(2),x V z≦1111100111(2) であり、

 各 z について x は、

 100000(2)≦x≦1111100111(2) の場合 999-31=968 通りと

 x≦11111(2) かつ x,z の下位から 4,5桁目が等しい 8 通りの 976 通り、

 よって、976・24=23424 通りあります。

.

スポンサーサイト



Comments 16

There are no comments yet.
ひとりしずか  
No title

やわらかな色合いがやさしい~

uch*n*an  
No title

うーむ,なかなか難しいですね。何らかの規則性があるだろうとは思い,
2のべき乗までは気付いたものの,2進法,排他的論理和までは思い付きませんでした。
私の解法は論理的というより演繹的で,規則性を見極めるために,
まず 10 * 10 を実際にやって結果から規則性を洗い出し,それをもとに,
8 * 8,12 * 12,を実際にやって規則性を修正し,さらに,6 * 6,14 * 14,で確認し,
9 * 9,11 * 11,でも一部修正でうまくいくのを確認し,1000 * 1000 に適用しました。
幾つもの実験で破綻はなかったので,結果にはそこそこ自信がありましたが,
念のためにプログラムも組んで調べたら,規則性はドンピシャ! うまくいきました。
ただ,その理由付けが直感的なもの以外はうまくいかず,引っかかっておりました。
2のべき乗から,2進法,排他的論理和,といけばよかったわけですが,
なかなか難しいです。

ゆうこ つれづれ日記  
No title

イカリソウですね。
こんなに黄色い色のイカリソウってお初です。
ナイス☆

tsuyoshik1942  
No title

ここ何問か「解けず!」が続いています。
本問も、「漢字6文字」[2^n...」等をヒントに粘ったのですが、結局、PCの力を借りてしまいました。

ところで、「1000問」秒読みですね!
数学の問題数としては大きな区切りですが、花・樹木等の写真の方も盛況ですね!
こちらはエンドレス(?)、とすれば、もしかして、まだ数学の方も続けていただけるのかと期待をしています。

スモークマン  
No title

グーテンアーベント ^^
さっぱりこの暗号も解読できず…^^;;
常連の方々はまったくもって凄いわ!!

1000問目という偉業達成まであとわずかですね☆
もう、1000問目はできてて、1001問目も貴殿の頭の中には浮かんでるものと予測しておりますです…Orz~

ニリンソウ  
No title

黄色の蜘蛛みたいな!
キバナイカリソウでも形はいろいろあったんですね。
我が家はまるっこい花でした。

ナイス

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
イカリソウの黄色はもっと色の薄いのが多いと思います。
柔らかな感じがする色合いですね。

ヤドカリ  
No title

uch*n*anさん、コメントをありがとうございます。
まず、0から始めると考えやすいですね。
少し書きだすと2のべき乗が絡むことは容易に分かりますが、
2進法で表したときの排他的論理和に結びつくとスッキリしますね。

ヤドカリ  
No title

ゆうこさん、コメントとナイス!をありがとうございます。
イカリソウの黄色はもっと色の薄いのが多いですね。
わたしもこんなに濃い黄色は初めてです。
今まで見たことのないものを見られて嬉しいです。

ヤドカリ  
No title

tsuyoshik1942さん、コメントをありがとうございます。
この問題は難しかったと思います。
ところで、「1000問」のあとはまだ言える段階でないです。
なお、数学の問題や解答だけの殺風景を避けるための花の写真ですので、
花がメインにならないよう、1枚だけにしています。
たくさん撮ったときはそれだけで記事にしています。

ヤドカリ  
No title

スモークマンさん、コメントをありがとうございます。
この暗号の解読は難しかったと思います。
1000問に向かって進んでいますが、
その後のことはまだ公言できる段階でないです。

ヤドカリ  
No title

ニリンソウさん、コメントをありがとうございます。
言われてみるとイカリソウって蜘蛛みたいな形ですね。
イカリソウに花が何色かあるのがいいですね。

さっちゃんこ  
No title

こんばんは♪
イカリソウは見たこと無いですが黄色のイカリソウを見せてもらうのも珍しい様です♪
可愛いですネ!!

ナイス♪

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!をありがとうございます。
そちらにはイカリソウは咲かないのですか?
明日は白いのをアップしますね。

樹☆  
No title

黄色のイカリソウがあるのですね。
白いのは見ることがありますが。。

ヤドカリ  
No title

樹ちゃん、コメントとナイス!をありがとうございます。
黄色のイカリソウは薄黄色しか見たことがなかったのですが、
このような濃い黄色もあったのですね。