Comprimento máximo das trajetórias no bilhar

Question

Considere o billard retangular discreto na rede com dimensões inteiras a*be nbolas com raio$\frac{\sqrt 2}{2}$e massa igual. Em uma etapa de tempo, a bola corre de um ponto da rede ao ponto vizinho na direção horizontal ou vertical. Quando duas bolas se encontram em pontos diagonais vizinhos, elas refletem de acordo com as leis da física, quando a bola atinge a fronteira, ela reflete de volta. Outros tipos de colisões são proibidos (interrompemos esta corrida e escolhemos outras posições de bola), em particular colisões com mais de 2 bolas. Este bilhar é reversível e todos os caminhos permitidos são cíclicos. Qual é o número máximo de passos antes que todas as bolas estejam na posição em que começaram, dependendo de a, be n? É exponencial ou polinomial quando n cresce linearmente e a razão de ae bpara né constante?
EDIT: Agora eu uso a modificação deste bilhar: as bolas são quadrados com diagonal 2 e diagonais paralelos aos eixos. Isso permite um novo tipo de colisão - reta (ângulo a ângulo). A distância de Manhattan entre os centros das praças deve ser sempre uniforme.

Answer 1

Calculei comprimentos de ciclos e contagens de diferentes comprimentos de ciclo para pequenos valores de bolas quadradas e obtive resultados que sugerem que ambos os números crescem exponencialmente. Quando a contagem de bolas aumenta em 1 potência do polinômio para comprimentos de ciclo ou contagens também aumenta aproximadamente em 1.

Resultados para comprimentos de ciclo de 6 bolas para diferentes tamanhos de rede:
6: 142
7: 740
8: 1214
9: 2836
10: 4978
11: 6260
12: 18974
13: 54248
14: 40902
15: 69684
16: 116994
17: 224644
18: 247622+
19: 152844+
20: 371832+
21: 921420+
22: 527196+
23: 260288+
25: 4574916+
29: 6751260+
33: 17788732+

Contagens de ciclo para 2 bolas:
tamanho de rede par: 5
tamanho de rede ímpar: 6
Contagens de ciclo para 3 bolas:
4: 3
5: 5
6: 13
7: 17
8: 31
9: 44
10: 58
11: 91
12: 121
13 : 150
14: 182
15: 243
16: 275
17: 345
18: 375
19: 461
20: 533
21: 615
22: 688
23: 806
24: 876
25: 989
26: 1072
27: 1230
28: 1328
29: 1470
30: 1600
31: 1806
32: 1898
Contagens de ciclo para 4 bolas:
4: 5
5: 11
6: 27
7: 46
8: 84
9: 130
10: 174
11: 271
12: 371
13: 486
14: 636
15: 860
16: 1065
17: 1364
18: 1677+
Contagens de ciclo para 6 bolas:
6: 22
7: 34
8: 93
9: 134
10: 177
11: 298
12: 386
13: 534+
14: 568+

Programa C com o qual obtive esses resultados (Mersenne twister de https://github.com/ESultanik/mtwister):

#include <inttypes.h>
#include <iso646.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "mtwister.h"


#define ball_len 4

MTRand randomize() {
    srand((unsigned int) time(NULL));
    MTRand mtrand = seedRand(rand());
    return mtrand;
}

int rnd(int r_bound, MTRand* p_mtrand) {
    return genRandLong(p_mtrand) % r_bound;
}

int* make_new_balls(int ball_count) {
    return (int*) malloc(ball_count * ball_len * sizeof(int));
}

int* get_ball(int* balls, int ball_num) {
    return balls + ball_len * ball_num; // x, y, v_x, v_y
}

int get_ball_prop(int* ball, int coord_or_v, int x_or_y) {
    return ball[coord_or_v * 2 + x_or_y];
}

void set_ball_prop(int* ball, int coord_or_v, int x_or_y, int val) {
    ball[coord_or_v * 2 + x_or_y] = val;
}

void inc_ball_prop(int* ball, int coord_or_v, int x_or_y, int val) {
    ball[coord_or_v * 2 + x_or_y] += val;
}

void mul_ball_prop(int* ball, int coord_or_v, int x_or_y, int val) {
    ball[coord_or_v * 2 + x_or_y] *= val;
}

void print_ball(int* ball) {
    printf("(%d, %d), (%d, %d)\n", ball[0], ball[1], ball[2], ball[3]);
}

void print_balls(int ball_count, int* balls) {
    printf("\n");
    for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
        int* ball = get_ball(balls, ball_num);
        print_ball(ball);
    }
}

int get_is_new_state_long(int ball_count, int* balls, int* first_balls) {
    for (int i = 0; i < ball_count * ball_len; ++i) {
        if (balls[i] != first_balls[i]) {
            return 1;
        }
    }
    return 0;
}

int run_two_dim_balls_lattice_with_square_balls(int field_0, int field_1, int ball_count, int* balls, int* first_balls, int* new_balls, int* collision_counts, int* close_counts, int* vs_history, int* coll_history, int* orig_balls) {
    int is_running = 1;
    int vs_history_pos = -ball_count * 2;
    int bit_history_pos = -field_0;
    int coll_num = 0;
    int* parity_ball;
    int iter_num = -1;
    while (is_running) {
        iter_num += 1;
        vs_history_pos += ball_count * 2;
        bit_history_pos += field_0;
        for (int ball0_num = 0; ball0_num < ball_count; ++ball0_num) {
            int* ball0 = get_ball(balls, ball0_num);
            if (get_ball_prop(ball0, 0, 0) < 0 or get_ball_prop(ball0, 0, 0) >= field_0 or get_ball_prop(ball0, 0, 1) < 0 or get_ball_prop(ball0, 0, 1) >= field_1) { // out of field
                return -1;
            }
            for (int ball1_num = ball0_num + 1; ball1_num < ball_count; ++ball1_num) {
                int* ball1 = get_ball(balls, ball1_num);
                if (abs(get_ball_prop(ball0, 0, 0) - get_ball_prop(ball1, 0, 0)) + abs(get_ball_prop(ball0, 0, 1) - get_ball_prop(ball1, 0, 1)) < 2) { // balls are too close
                    return -1;
                }
            }
        }
        for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
            close_counts[ball_num] = 0;
        }
        for (int ball0_num = 0; ball0_num < ball_count; ++ball0_num) {
            int* ball0 = get_ball(balls, ball0_num);
            for (int ball1_num = ball0_num + 1; ball1_num < ball_count; ++ball1_num) {
                int* ball1 = get_ball(balls, ball1_num);
                if (abs(get_ball_prop(ball0, 0, 0) - get_ball_prop(ball1, 0, 0)) == 1 and abs(get_ball_prop(ball0, 0, 1) - get_ball_prop(ball1, 0, 1)) == 1) {
                    close_counts[ball0_num] += 1;
                    close_counts[ball1_num] += 1;
                }
            }
        }
        for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
            if (close_counts[ball_num] > 1) { // more than 2 balls are near each other
                return -1;
            }
        }
        for (int i = 0; i < ball_count * ball_len; ++i) {
            new_balls[i] = balls[i];
        }
        // handle collisions
        int is_all_collisions_resolved = 0;
        int coll_iter_num = -1;
        while (not is_all_collisions_resolved) {
            coll_iter_num += 1;
            if (coll_iter_num == 1000) {
                return -1;
            }
            for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
                collision_counts[ball_num] = 0;
            }
            for (int ball0_num = 0; ball0_num < ball_count; ++ball0_num) {
                int* ball0 = get_ball(balls, ball0_num);
                int* new_ball0 = get_ball(new_balls, ball0_num);
                // collisions with borders
                if (get_ball_prop(ball0, 0, 0) == 0 and get_ball_prop(ball0, 1, 0) < 0) {
                    collision_counts[ball0_num] += 1;
                    mul_ball_prop(new_ball0, 1, 0, -1);
                } else if (get_ball_prop(ball0, 0, 0) == field_0 - 1 and get_ball_prop(ball0, 1, 0) > 0) {
                    collision_counts[ball0_num] += 1;
                    mul_ball_prop(new_ball0, 1, 0, -1);
                } else if (get_ball_prop(ball0, 0, 1) == 0 and get_ball_prop(ball0, 1, 1) < 0) {
                    collision_counts[ball0_num] += 1;
                    mul_ball_prop(new_ball0, 1, 1, -1);
                } else if (get_ball_prop(ball0, 0, 1) == field_1 - 1 and get_ball_prop(ball0, 1, 1) > 0) {
                    collision_counts[ball0_num] += 1;
                    mul_ball_prop(new_ball0, 1, 1, -1);
                }
                // collisions with other balls
                for (int ball1_num = ball0_num + 1; ball1_num < ball_count; ++ball1_num) {
                    int* ball1 = get_ball(balls, ball1_num);
                    int* new_ball1 = get_ball(new_balls, ball1_num);
                    if (abs(get_ball_prop(ball0, 0, 0) - get_ball_prop(ball1, 0, 0)) == 1 and abs(get_ball_prop(ball0, 0, 1) - get_ball_prop(ball1, 0, 1)) == 1) {
                        // parallel collisions
                        if (get_ball_prop(ball0, 1, 0) == -get_ball_prop(ball1, 1, 0) and (get_ball_prop(ball0, 0, 0) - get_ball_prop(ball1, 0, 0)) * get_ball_prop(ball0, 1, 0) < 0) {
                            collision_counts[ball0_num] += 1;
                            collision_counts[ball1_num] += 1;
                            if (get_ball_prop(ball0, 0, 1) > get_ball_prop(ball1, 0, 1)) {
                                set_ball_prop(new_ball0, 1, 1, 1);
                                set_ball_prop(new_ball1, 1, 1, -1);
                            } else {
                                set_ball_prop(new_ball0, 1, 1, -1);
                                set_ball_prop(new_ball1, 1, 1, 1);
                            }
                            set_ball_prop(new_ball0, 1, 0, 0);
                            set_ball_prop(new_ball1, 1, 0, 0);
                        } else if (get_ball_prop(ball0, 1, 1) == -get_ball_prop(ball1, 1, 1) and (get_ball_prop(ball0, 0, 1) - get_ball_prop(ball1, 0, 1)) * get_ball_prop(ball0, 1, 1) < 0) {
                            collision_counts[ball0_num] += 1;
                            collision_counts[ball1_num] += 1;
                            if (get_ball_prop(ball0, 0, 0) > get_ball_prop(ball1, 0, 0)) {
                                set_ball_prop(new_ball0, 1, 0, 1);
                                set_ball_prop(new_ball1, 1, 0, -1);
                            } else {
                                set_ball_prop(new_ball0, 1, 0, -1);
                                set_ball_prop(new_ball1, 1, 0, 1);
                            }
                            set_ball_prop(new_ball0, 1, 1, 0);
                            set_ball_prop(new_ball1, 1, 1, 0);
                        // perpendicular collisions
                        } else if (get_ball_prop(ball0, 0, 0) + get_ball_prop(ball0, 1, 0) == get_ball_prop(ball1, 0, 0) + get_ball_prop(ball1, 1, 0) and get_ball_prop(ball0, 0, 1) + get_ball_prop(ball0, 1, 1) == get_ball_prop(ball1, 0, 1) + get_ball_prop(ball1, 1, 1)) {
                            collision_counts[ball0_num] += 1;
                            collision_counts[ball1_num] += 1;
                            int temp0 = get_ball_prop(ball1, 1, 0);
                            int temp1 = get_ball_prop(ball1, 1, 1);
                            int temp2 = get_ball_prop(ball0, 1, 0);
                            int temp3 = get_ball_prop(ball0, 1, 1);
                            set_ball_prop(new_ball0, 1, 0, temp0);
                            set_ball_prop(new_ball0, 1, 1, temp1);
                            set_ball_prop(new_ball1, 1, 0, temp2);
                            set_ball_prop(new_ball1, 1, 1, temp3);
                        } 
                    // direct collisions
                    } else if ( (abs(get_ball_prop(ball0, 0, 0) - get_ball_prop(ball1, 0, 0)) == 2 and get_ball_prop(ball0, 0, 1) == get_ball_prop(ball1, 0, 1)) or (abs(get_ball_prop(ball0, 0, 1) - get_ball_prop(ball1, 0, 1)) == 2 and get_ball_prop(ball0, 0, 0) == get_ball_prop(ball1, 0, 0)) ) {
                        if ( (get_ball_prop(ball0, 0, 0) + get_ball_prop(ball0, 1, 0) == get_ball_prop(ball1, 0, 0) + get_ball_prop(ball1, 1, 0)) and (get_ball_prop(ball0, 0, 1) + get_ball_prop(ball0, 1, 1) == get_ball_prop(ball1, 0, 1) + get_ball_prop(ball1, 1, 1)) ) {
                            collision_counts[ball0_num] += 1;
                            collision_counts[ball1_num] += 1;
                            mul_ball_prop(new_ball0, 1, 0, -1);
                            mul_ball_prop(new_ball0, 1, 1, -1);
                            mul_ball_prop(new_ball1, 1, 0, -1);
                            mul_ball_prop(new_ball1, 1, 1, -1);
                        }
                    }
                } // for ball1_num
            } // for ball0_num
            is_all_collisions_resolved = 1;
            for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
                if (collision_counts[ball_num] > 0) {
                    is_all_collisions_resolved = 0;
                    if (collision_counts[ball_num] > 1) {
                        return -1;
                    }
                }
            }
            for (int i = 0; i < ball_count * ball_len; ++i) {
                balls[i] = new_balls[i];
            }
        } // while (not is_all_collisions_resolved)
        if (iter_num == 0) {
            for (int i = 0; i < ball_count * ball_len; ++i) {
                first_balls[i] = balls[i];
            }
        } else {
            is_running = get_is_new_state_long(ball_count, balls, first_balls);
        }
        for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
            int* ball = get_ball(balls, ball_num);
            inc_ball_prop(ball, 0, 0, get_ball_prop(ball, 1, 0));
            inc_ball_prop(ball, 0, 1, get_ball_prop(ball, 1, 1));
        }
    } // while (is_running)
    return iter_num;
}

int main() {
    MTRand mtrand = randomize();
    int ball_count = 6;
    int field_0 = 8;
    int field_1 = field_0;
    printf("ball_count, field_0 = %d, %d\n", ball_count, field_0);
    int* balls = make_new_balls(ball_count);
    int* first_balls = make_new_balls(ball_count);
    int* orig_balls = make_new_balls(ball_count);
    int* new_balls = make_new_balls(ball_count);
    int v_count = 4;
    int* vs = (int*) malloc(v_count * 2 * sizeof(int));
    int history_len = 1000000;
    int* vs_history = (int*) malloc(history_len * sizeof(int));
    int* bit_history = (int*) malloc(history_len * sizeof(int));
    int* coll_history = (int*) malloc(history_len * sizeof(int));
    vs[0] = -1; vs[1] = 0; vs[2] = 0; vs[3] = -1; vs[4] = 0; vs[5] = 1; vs[6] = 1; vs[7] = 0;
    int vs_history_pos;
    int bit_history_pos;
    int* close_counts = (int*) malloc(ball_count * sizeof(int));
    int* collision_counts = (int*) malloc(ball_count * sizeof(int));
    int v;
    int bit;
    int iter_count;
    int run_count = 0;
    int max_iter_count = -1;
    int horiz_ball_count;
    int more_count = 0;
    int max_coord_pair_count = field_0 * field_1;
    int* coord_pairs = (int*) malloc(max_coord_pair_count * 2 * sizeof(int));
    int coord_pair_count = 0;
    for (int i_x = 0; i_x < field_0; ++i_x) {
        for (int i_y = 0; i_y < field_1; ++i_y) {
            if ((i_x + i_y) % 2 == 1) {
                continue;
            }
            coord_pairs[coord_pair_count*2] = i_x;
            coord_pairs[coord_pair_count*2 + 1] = i_y;
            ++coord_pair_count;
        }
    }
    printf("coord_pair_count = %d\n\n", coord_pair_count);
    int rnd0, rnd1;
    int zero_bit;
    int* ball;
    int pair_num;
    int iter_counts_len = 100000000;
    int* iter_counts = (int*) malloc(iter_counts_len * sizeof(int));
    int iter_counts_pos = 0;
    for (int i = 0; i < iter_counts_len; ++i) {
        iter_counts[i] = 0;
    }
    int is_iter_count_found;
    int max_wait = 0;
    int prev_change_num = 0;
    while (1) {
        run_count += 1;
        for (int ball_num = 0; ball_num < ball_count; ++ball_num) {
            ball = get_ball(balls, ball_num);
            pair_num = rnd(coord_pair_count, &mtrand);
            ball[0] = coord_pairs[pair_num*2];
            ball[1] = coord_pairs[pair_num*2 + 1];
            zero_bit = rnd(2, &mtrand);
            ball[3 - zero_bit] = rnd(2, &mtrand)*2 - 1;
            ball[2 + zero_bit] = 0;
        }
        iter_count = run_two_dim_balls_lattice_with_square_balls(field_0, field_1, ball_count, balls, first_balls, new_balls, collision_counts, close_counts, vs_history, coll_history, orig_balls);
        if (iter_count > 0) {
            is_iter_count_found = 0;
            for (int i = 0; i < iter_counts_pos; ++i) {
                if (iter_counts[i] == iter_count) {
                    is_iter_count_found = 1;
                    break;
                }
            }
            if (not is_iter_count_found) {
                iter_counts[iter_counts_pos] = iter_count;
                iter_counts_pos += 1;
                if (run_count - prev_change_num > max_wait) {
                    max_wait = run_count - prev_change_num;
                }
                prev_change_num = run_count;
            }
        }
        if (iter_count > max_iter_count) {
            max_iter_count = iter_count;
            printf("run_count, max_iter_count = %d, %d\n", run_count, max_iter_count);
        }
        if (run_count % 1000000 == 0) {
            printf("\n");
            printf("ball_count, field_0, run_count, max_iter_count, max_wait, iter_counts_pos = \n%d, %d, %d, %d, %d, %d\n", ball_count, field_0, run_count, max_iter_count, max_wait, iter_counts_pos);
        }
    }
    printf("ball_count, field_0, max_iter_count = %d, %d, %d\n", ball_count, field_0, max_iter_count);
    return 0;
}