4
$\begingroup$

Consider discrete rectangular billard on lattice with integer dimensions a*b and n balls with radius $\frac{\sqrt 2}{2}$ and equal mass. In one time step ball runs from one lattice point to neighboring point in horizontal or vertical direction. When two balls meet on neighboring diagonal points they reflect according to laws of physics; when ball reaches border, it reflects back. Other types of collisions are forbidden (we halt this run and choose other ball positions), in particular collisions with more than 2 balls. This billiard is reversible and all allowable paths are cyclic. What is the maximal number of steps before all balls will be in position in which they started depending on a, b and n? Is it exponential or polynomial when n grows linearly and ratio of a and b to n is constant?
EDIT: Now I use modification of this billiard: balls are squares with diagonal 2 and diagonals parallel to axes. This allows new type of collision - straight (angle to angle). Manhattan distance between centers of squares should always be even.

Improve this question
$\endgroup$
6
  • $\begingroup$ Do all balls have the same mass? Also, I am not quite sure what "reflects according to the laws of physics" means, because unless I am mistaken a ball that has experienced a collision will not move on lattice points anymore (after 1 time step the ball will not be on a lattice point). $\endgroup$
    – Random
    Sep 1, 2020 at 14:47
  • $\begingroup$ Yes, mass is the same. Some collisions can reflect balls perpendicularly to their previous movement. You can test this here: phet.colorado.edu/sims/collision-lab/collision-lab_en.html ("advanced" page) $\endgroup$
    – DSblizzard
    Sep 1, 2020 at 15:49
  • $\begingroup$ Perhaps consider the case with square board first, and do some computer simulations, and look for hits in the oeis? $\endgroup$
    – Per Alexandersson
    Sep 1, 2020 at 19:33
  • $\begingroup$ Already tried this without success. And computer can compute only very small boards with irregular sequence of path lengths, so I cannot discover pattern. $\endgroup$
    – DSblizzard
    Sep 1, 2020 at 19:59
  • $\begingroup$ Would you initiate the system?! What balls are present, and what are their moving directions (if any) at the moment ZERO? $\endgroup$
    – Wlod AA
    Sep 25, 2022 at 18:53

1 Answer 1

Reset to default
1
$\begingroup$

I computed lengths of cycles and counts of different cycle lengths for small values of square balls and obtained results which suggest that both of these numbers grow exponentially. When ball count raises by 1 power of polynomial for cycle lengths or counts also raises approximately by 1.

Results for cycle lengths for 6 balls for different lattice sizes:
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+

Cycle counts for 2 balls:
even lattice size: 5
odd lattice size: 6
Cycle counts for 3 balls:
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
Cycle counts for 4 balls:
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+
Cycle counts for 6 balls:
6: 22
7: 34
8: 93
9: 134
10: 177
11: 298
12: 386
13: 534+
14: 568+

C program with which I obtained these results (Mersenne twister from 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;
}
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.