■
■借りず１３枚.:エレガントな解法についてメモ(2)
ひたすら思いつきをメモ中
KAMADAさん2001年11月の日記を精読中。エンピツと消しゴムが欲しい。
１３と天秤と３
あらためて驚きを感じました。借りず１３枚と天秤３回計量。影に隠れた３進数。
4=30+31
13=30+31+32
関係式はなんとなく知っていたのだけれども、書き下して見るとやっぱり美しい。
もうひとつの１３と天秤
これも驚いたのです。
分銅を３種類用意します。1g, 3g, 9g の３種類。上皿天秤で例えば2gを1回の計量で量りたいとするならば左に1g,右に3gを乗せる、そして（たとえば薬品など）を左にのせてバランスがとれればその薬品は2Gです。この要領で量れる重さは、1g単位で、13gまで。分銅を、4種類とし、1=30g, 3=31g, 9=32g, 27=33g, を用意すると、1g単位で、40gまで。この40という数字は、借りず4回計量でニセモノ1枚を分別可能な最大の枚数と等しい。
平衡３進数の理解？
『上皿天秤で例えば2gを1回の計量で量りたいとするならば左に3g,右に1gを乗せる、』、これが平衡３進数のひとつの理解の仕方のようです。2を平衡３進数で表現。メモ的な書き方だがのちのちの私個人の理解の為に書いておくと、こうなるらしい。
[ 1, -1 ]3=1*31 + (-1)*30
なるほど、これが平衡３進数なのだと了解。
ここまで理解したのでもう一度KAMADAさんの日記を読みに行くことに
証明のキモが自明らしく省略されているので自分で作らなくては。
なにか進展があれば、とりまとめをこの日記に書くかもしれません。書かないかもしれません。（コラ）
今書いているところで、驚きというかオイシイところは食い尽くしたかもしれません。そうそう、コンピュータアルゴリズムとの関係を知りたいなァ。平衡３進数を知っていると便利なことってあるのかも。あと、まだまだ確認もしていないのですが、とある進数との関わりも知りたい。
とある進数とあいまいに書きましたが、これ、正式の名前を知らないのですよ。次のような説明で思い出せる人は是非私に教えてください。
よくWebページなどに飾ってあるカウンターを取り上げます。今、カウンターが９９７だとします。１階踏むと９９８になります。この時、もとの数字９９７と今の数字９９８とを比べると、文字としては一桁分、７から８に変ります。もう１回踏むと９９８から９９９になりますが、文字としては一桁分、８が９になります。ところが、もう１回踏むとカウンターは１０００になります。文字としては、４桁も変ります。Webページのカウンターであれば実質１枚の画像出力ですから問題はないのですけれど、これを困った困ったと思う人もいるわけです。あのカウンターが実物として構成されているものを見たことがありますか？メーターか何かで見ませんか？繰りあがる時に一斉に各桁の表示が変わる時に、力学的に普段よりも余計な負荷がかかっていないでしょうか。精密機器において物理的なカウンターを用意する場合にこのような余計な負荷がかかる一瞬があると精度が低くなる場合も想定できます。ですのでこれを改善する為に、いついかなる時でも、数を１だけ増やしたときに、変更すべき桁の個数を１個だけにしてしまえないか、このことによりカウンターの負荷を時間的に平準化できないか、ということになります。実際問題として、各桁が０と１の２種類の表示だけだとして、平準化された繰りあがりを持つような数値表現を可能とする方法があることを、どこかで読みました。どのようにしていたのかを思い出せないのですがね。直観なのですが、この方法と平衡３進数との間に面白い関係が出てくるのではと思ったのです。へんな直観ですねぇ。確か補数表示を併用するのだったかなぁ。。。いや排他的論理和だったか？忘れたよぉ、一度だけ雑誌で読んだ記事だもの。
グレイ
ここまで書いていて我が大脳からなんとなくグレイという単語が。グレイナンバーを検索。グレイというグループのナンバーのもより。音楽かよ。次、グレイカウンター。ん？ヒットしてきたっぽい。次、グレイ・コード・カウンタ。ヒット！！。ふぅむ、回路に使われていますか。チャタリングでもするのを防止するのかな？ヒゲ防止ってなんだろう。というわけでメモ。あとで読もう。Verilogのマニュアル ver 1.0 おまけ４．順序回路補足
というわけでグレイコードの例を上記マニュアルから引用。
4'b0000：gray = 4'b0001;
4'b0001：gray = 4'b0011;
4'b0011：gray = 4'b0010;
4'b0010：gray = 4'b0110;
4'b0110：gray = 4'b0111;
4'b0111：gray = 4'b0101;
4'b0101：gray = 4'b0100;
4'b0100：gray = 4'b1100;
4'b1100：gray = 4'b1101;
4'b1101：gray = 4'b1111;
4'b1111：gray = 4'b1110;
4'b1110：gray = 4'b1010;
4'b1010：gray = 4'b1011;
4'b1011：gray = 4'b1001;
4'b1001：gray = 4'b1000;
4'b1000：gray = 4'b0000;
右側がグレイコード。順に見ていくと１ビットずつしか変化していない。ちなみにgreyは灰色のことではない。こんな着想をした人の人名のはず。グレイさんは偉大だ。でもこれと平衡３進数との間になんの関係があるのかわからない。なんとなくそんな気がするだけなのに。わはは。
神の順序
いやぁ調べて見てビックリ。グレイコードで実数を表現できるなんて想像もしていませんでした。フラクタルとも関係が。すげぇ。神即自然。グレイコードと実数の記事はとても刺激的。
１０進でのグレイコードの一例。他にもあるんだろう、きっと。
0
1
2
3
4
5
6
7
8
9
19 aka 10
18 aka 11
17 aka 12
16 aka 13
15 aka 14
14 aka 15
13 aka 16
12 aka 17
11 aka 18
10 aka 19
20
21
22
..
..
99 aka 90
98 aka 91
97 aka 92
96 aka 93
95 aka 94
94 aka 95
93 aka 96
92 aka 97
91 aka 98
90 aka 99
190 aka 100 !
小学生には教えてはいけないような気がする。
