パスワードを忘れた？ アカウント作成
Close

GeoJさんのトモダチの日記、みんなの日記も見てね。 Idle.slashdot.jpは、あなたの人生において完全な時間の浪費です。見るなよ、見るなよ。

113806 journal

GeoJの日記： その後の進展

日記 by GeoJ

定義：
前回までの定義に加えて以下を定義する．
C (n,i)＝{B＋c | B∈B(n,i), c∈ℤ}　：　解A(n,i)の部分和の列に法sの下で任意の整数を加えてできる列集合の族．
ただし，∀B∈B(n,i), ∀c∈ℤに対してB＋c＝{b＋c mod s | b∈B}とする．

定義からB (n,i)⊂C (n,i)となる．
特にB (n,i)＝{C∈C (n,i) | 0∈C}である．
また，|B (n,i)|＝n，|C (n,i)|＝Sである．

さらに，任意のx,y∈ℤ，x≠y mod sに対して，C (n,i)(x,y)＝B (n,i)(y－x mod s)＋xとすると，C (n,i)(x,y)∈x, yを満たすC (n,i)の元を一意に指定できる．

以下、前回と同様にbenihitode予想を正しいものと仮定する。

補題：
命題：
∀C (n,i)に対し，∃Cid (n,i)∈C (n,i)があって，Cid (n,i)＝q・Cid (n,i)．

証明：
∃m∈ℤがあってn＝3m+1又はn＝3m+2となる時，前回の結論からB＝q・Bとなる孤立列B∈B (n,i)が存在するのでCid (n,i)＝Bとなる．
したがって，n＝3mとなる時のみを証明すればよい．

任意のx,y∈ℤ，x≠y mod sに対して，前回の結論から，B (n,i)(y-x)は三つ組列の兄弟q・B (n,i)(y-x)＝B (n,i)(qy-qx)及びq2・B (n,i)(y-x)＝B (n,i)(q2y-q2x)を持つ．
それぞれ変形してC (n,i)(qx,qy)＝B (n,i)(qy-qx)＋qx＝q・B (n,i)(y-x)＋qx，C (n,i)(q2x,q2y)＝B (n,i)(q2y-q2x)＋q2x＝q2・B (n,i)(y-x)＋q2xと書ける．
したがって，q・C (n,i)(x,y)＝C (n,i)(qx,qy)，q2・C (n,i)(x,y)＝C (n,i)(q2x,q2y)である．

C (n,i)(x,y)≠C (n,i)(qx,qy)であれば，C (n,i)(x,y)，C (n,i)(qx,qy)，C (n,i)(q2x,q2y)は三つ組列を形成する．
ここで，C (n,i)がすべて三つ組列であるとすると，C (n,i)の元の個数は3の倍数になるはずだが，実際には|C (n,i)|＝3m(3m-1)+1なので矛盾する．
ゆえにC (n,i)(xid,yid)＝C (n,i)(qxid,qyid)となるC (n,i)(xid,yid)∈C (n,i)が一つ以上存在しなければならない．

この時，Cid (n,i)＝C (n,i)(xid,yid)となる（証明終わり）．

結論：
命題より，すべての解のそれぞれに対してC=q・Cとなる拡張部分和列が一つ以上存在することになる．
言いかえれば，C=q・Cとなるすべての拡張部分和列を探索すれば，すべての解を網羅できることが（benihitode予想の下に）証明できた．

113003 journal

GeoJの日記： benihitode氏のあれ

日記 by GeoJ

定義：
n　：　球の個数．3≦n．
s＝n・(n - 1) + 1　：　全ての球の合計．
q＝n - 1　：　特にqが素数pの冪の時，q＝pkとする．
A n　：　解集合の族．
A n∋A(n,i)={a(n,i,0), a(n,i,1), ..., a(n,i,n-1)}　：　解集合．0≦i≦|A n| - 1．
ただし，回転して合同な解は同一解，鏡像反転して合同な解は別解として扱うものとし，a(n,i,0)=1とする．
B (n,i)　：　解A(n,i)の部分和の列集合の族．
B (n,i)∋B(n,i,j)＝{b(n,i,j,0), b(n,i,j,1), ..., b(n,i,j,n-1)}　：　解A(n,i)の部分和の列集合．0≦j≦n-1．
ただし，b(n,i,j,0)＝0，b(n,i,j,l)＝∑r＝0...l-1 a(n,i,j+r)（添え字j+rはnを法とする）．

benihitode予想：
∀B(n,i,j)に対してB (n,i)∋p・B(n,i,j)＝{p・b mod s | b∈B(n,i,j)}．

以下、benihitode予想を正しいものと仮定する。

補題：
∀B (n,i), 0＜∀t≦s-1に対してB(n,i,j)∋tとなるB(n,i,j)∈B (n,i)が唯一つ存在する．

（補題の証明は解の部分和の定義から自明のため省略する．）

以後、補題よりB(n,i,j)∋tとなるB(n,i,j)∈B (n,i)をB (n,i)(t)と書く。すなわちB(n,i,j)＝B (n,i)(t)∈B (n,i)

命題：
∃B (n,i)，∃bでB (n,i)(b)∋q・bならば，B (n,i)(b)∋q2・b．

証明：
q・B (n,i)(b)＝{q・t mod s | t∈B (n,i)(b)}を考えると，B (n,i)(b)∋bよりq・B (n,i)(b)∋q・bである．
benihitode予想より、k回繰り返して適用するとq・B (n,i)(b)＝pk・B (n,i)(b)∈B (n,i)であり，補題よりq・bを含むB (n,i)の元は唯一つしか存在しないので，B (n,i)(b)＝q・B (n,i)(b)．
したがって，B (n,i)(b)∋q・bよりq・B (n,i)(b)∋q2・bなので，B (n,i)(b)∋q2・b　（証明終わり）．

結論：
定義よりq3＝1（mod s）であるので，任意の整数rに対してB (n,i)(b)＝q3r・B (n,i)(b)である．
よって命題から，B (n,i)(b)∋q・bならば，任意の整数rに対してB (n,i)(b)＝qr・B (n,i)(b)である．
逆に，B (n,i)(b) ∌ q・bならば，任意の整数rに対してB (n,i)(b)≠q3r±1・B (n,i)(b)である．

このことは，部分和の列集合がq倍することで順に入れ替わる3つ組の列とq倍して自身に戻る孤立列とで構成されることを示す．このうちの孤立列は，さらにそこに含まれる部分和自体がq倍することで順に入れ替わる3つ組の値とq倍して自身に戻る孤立した値とで構成されることもわかる．

q倍して自身に戻るような値は0があるが，それ以外ではsが3の倍数の時にs/3及び2s/3が該当するのみ(sが9の倍数になることはないため)である．このsが3の倍数の場合とはn=3m+2となる場合であるため，孤立列は二つの孤立数を含まなければならない．この場合，0は必ず含まれるため，B (n,i)(s/3)とB (n,i)(2s/3)の二つが孤立列となり，残りはm組の三つ組の列となる．

逆にn=3mとなる場合は，唯一の孤立数の0が必ず含まれるため，残りの3m-1個の値は三つ組を構成できず孤立列は作られない．全てがm組の三つ組の列となる．

また，n=3m+1となる場合は，唯一の孤立数の0が必ず含まれ，残りの3m個の値は三つ組を構成して孤立列になることができる．列が3つ組を組むと一つ余ることから最低でも一つの孤立列が含まれることが分かるが，さらに3組単位で孤立列が含まれるかどうかについては今のところ不明である．なお，この場合はqが素数の冪乗になるためにはn=3k+1にならなければならないので，もう少し特殊な戦略が存在する可能性もある．

孤立列の探索にはいくつか有利な点があるが，残りはまた後で．

110211 journal

GeoJの日記： WindVoice氏のあれ

日記 by GeoJ
/*
** necklace.c
**     2009-06-19: Correction about the inline result for case "3".
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef unsigned int uint;

void usage(FILE * f, char * binname)
{
    fprintf(f, "Usage: %s size\n", binname);
}

void set_ball(int * balls, int size, int index, int ball)
{
    balls[index - size] = ball;
    balls[index] = ball;
    balls[index + size] = ball;
}

int get_bit(uint * bits, uint n)
{
    return (bits[(n >> 5)] >> (n & 0x001f)) & 1;
}

int set_bit(uint * bits, uint n)
{
    uint shift, bit;
    bits += (n >> 5);
    bit = (1ul << (n & 0x001f));
    if(*bits & bit) {
        return 1;
    } else {
        *bits |= bit;
        return 0;
    }
}

void clear_bit(uint * bits, uint n)
{
    bits[n >> 5] ^= (1ul << (n & 0x001f));
}

int count_successive_bits(uint * bits)
{
    int c = 0;
    uint last;
    while(*bits == 0xfffffffful) {
        c += 32;
        bits++;
    }
    last = *bits;
    while(last & 1) {
        c++;
        last >>= 1;
    }
    return c;
}

int countup(int * balls, uint * bits, int size, int index)
{
    int width, from, to, sum, i;
    set_bit(bits, balls[index]);
    for(width = 2; width < size; width++) {
        to = index + width;
        sum = 0;
        for(i = index; i < to; i++) {
            if(balls[i]) {
                sum += balls[i];
            } else {
                to = i;
            }
        }
        from = to - width;
        i = index;
        while(from < i--) {
            if(balls[i]) {
                sum += balls[i];
            } else {
                from = i + 1;
            }
        }
        if(to < from + width) {
            return 1;
        }
        if(set_bit(bits, sum)) {
            return 0;
        }
        while(index < --to) {
            if(balls[--from] && balls[to]) {
                sum += balls[from] - balls[to];
                if(set_bit(bits, sum)) {
                    return 0;
                }
            } else {
                break;
            }
        }
    }
    if(index == to && balls[index + 1]) {
        sum += balls[index + 1];
        if(set_bit(bits, sum)) {
            return 0;
        }
    }
    return 1;
}

int permute(int * last, int size, int len, int remain)
{
    int i;
    int ball;
    ball = count_successive_bits((uint *) (last + size * 3));
    if(remain == 0) {
        if(ball <= size * (size - 1) + 1) {
            return 0;
        }
        fprintf(stdout, "%d", last[0]);
        if(last[1] < last[size - 1]) {
            for(i = 1; i < size; i++) {
                fprintf(stdout, " %d", last[i]);
            }
        } else {
            for(i = size - 1; 0 < i; i--) {
                fprintf(stdout, " %d", last[i]);
            }
        }
        fprintf(stdout, "\n");
        fflush(stdout);
        return 1;
    } else if(remain < ball) {
        return 0;
    } else {
        int * current, * balls;
        uint * bits;
        int result = 0;
        remain -= ball;
        current = last + len;
        balls = current + size;
        bits = (uint *) (balls + size * 2);
        for(i = 1; i < size; i++) {
            if(last[i] == 0) {
                memcpy(current, last, len);
                set_ball(balls, size, i, ball);
                if(countup(balls, bits, size, i)) {
                    result += permute(current, size, len, remain);
                }
            }
        }
        return result;
    }
}

int main(int argc, char ** argv)
{
    int size, len, half, sum, result, i;
    int * buffer, * balls;
    uint * bits;
    char dummy[2];
    if(argc == 1) {
        usage(stdout, argv[0]);
        exit(0);
    }
    if(2 < argc || sscanf(argv[1], "%ld%1s", &size, dummy) != 1 || size < 1) {
        fprintf(stderr, "Error: Invalid Argument.\nArgument shall be a positive integer as size of neckless.\n");
        usage(stderr, argv[0]);
        exit(1);
    }
    switch(size) {
    case 1:
        fprintf(stdout, "For 1 ball:\n1\n");
        result = 1;
        break;
    case 2:
        fprintf(stdout, "For 2 balls:\n1 2\n");
        result = 1;
        break;
    case 3:
        fprintf(stdout, "For 3 balls:\n1 2 4\n");
        result = 1;
        break;
    case 4:
        fprintf(stdout, "For 4 balls:\n1 2 6 4\n1 3 2 7\n");
        result = 2;
        break;
    default:
        fprintf(stdout, "For %d balls:\n", size);
        half = (size + 1) / 2;
        sum = (size * (size - 1)) + 1;
        len = sizeof(int) * ((sum + 1) / 32 + 1 + size * 3);
        buffer = (int *) malloc(len * (size - 1));
        if(buffer == 0) {
            fprintf(stderr, "Error: Memory allocation Failure.\nTry with lesser size, or kill other processes and assign more swaps.\n");
            usage(stderr, argv[0]);
            exit(1);
        }
        memset(buffer, 0, len * (size - 1));
        balls = buffer + size;
        bits = (uint *) (buffer + size * 3);
        set_ball(balls, size, 0, 1);
        set_ball(balls, size, 1, 2);
        *bits = 0x000ful;
        result = permute(buffer, size, len, sum - 3);
        set_ball(balls, size, 1, 0);
        *bits = 0x0007ul;
        for(i = 2; i < half; i++) {
            set_ball(balls, size, i, 2);
            result += permute(buffer, size, len, sum - 3);
            set_ball(balls, size, i, 0);
        }
        if((size & 1) == 0) {
            int last;
            last = half - 1;
            set_ball(balls, size, half, 2);
            set_ball(balls, size, 1, 3);
            *bits = 0x001ful;
            result += permute(buffer, size, len, sum - 6);
            set_ball(balls, size, 1, 0);
            *bits = 0x000ful;
            for(i = 2; i < last; i++) {
                set_ball(balls, size, i, 3);
                result += permute(buffer, size, len, sum - 6);
                set_ball(balls, size, i, 0);
            }
            set_ball(balls, size, last, 3);
            *bits = 0x002ful;
            result += permute(buffer, size, len, sum - 6);
        }
    }
    if(result == 0) {
        fprintf(stdout, "No pattern was found.\n");
    } else if(result == 1) {
        fprintf(stdout, "Totally, 1 pattern was found.\n");
    } else {
        fprintf(stdout, "Totally, %d patterns were found.\n", result);
    }
    exit(0);
}
102045 journal

GeoJの日記： 「純国産野菜」の広告を見て、あなたは？ 2

日記 by GeoJ

おいしかったのでまた買いたい。
飲んだけどいまいち。
申込み損ねたけど興味はある。
伊藤園の他の商品を買いました。
飲み物は○○しか飲みません。
広告がうるさかった。
広告は消してるので見てません。
スラドの先行きが心配。

# フィードバックは必要だよね。
# 6/1以降に国民投票でお願いします。

102042 journal

GeoJの日記： M1

日記 by GeoJ

12回目。4ポイント。
前回はちゃんと「11回目。4ポイント。」と書いたつもりがアップされてなかった。
ちなみにその時は伊藤園の広告が始まったころで、「伊藤園の広告に[+1:興味深い]モデしたかった。」とも書いてた。
コメントじゃなく日記や記事のエントリにモデできるようにすると何がおこるんだろう。

73475 journal

GeoJの日記： M1

日記 by GeoJ

7回目。4ポイントに増えてしまう。
カルマを減らすにはどうしたらいいんだっけ。＜そうじゃないだろ。

71159 journal

GeoJの日記： M1

日記 by GeoJ

昨日。6回目。3ポイントなのですぐ使い切る。
M2も一度に3ポイントでかわりに3倍廻って来るぐらいがつけやすいのに。

typodupeerror

192.168.0.1は、私が使っている IPアドレスですので勝手に使わないでください --- ある通りすがり