Written by u/VirtualParticipation on Reddit.
In response to this post: https://www.reddit.com/r/askmath/comments/1fib0ss/if_anyone_could_help_me_provedisprove_the/

Day 1
Boat 1: 18 10 21 6  22 3  
Boat 2: 7  16 9  17 8  23 
Boat 3: 5  24 14 13 1  20 
Boat 4: 11 19 12 15 2  4  

Day 2
Boat 1: 16 5  24 19 2  18 
Boat 2: 12 7  3  9  14 21 
Boat 3: 22 4  1  23 10 17 
Boat 4: 11 20 6  15 8  13 

Day 3
Boat 1: 23 14 2  19 3  8  
Boat 2: 18 17 12 10 13 20 
Boat 3: 11 7  1  15 21 16 
Boat 4: 5  9  22 4  24 6  

Day 4
Boat 1: 24 7  10 12 8  5  
Boat 2: 9  3  4  20 16 13 
Boat 3: 11 23 22 15 18 14 
Boat 4: 21 6  1  19 17 2  

Day 5
Boat 1: 23 24 13 5  20 21 
Boat 2: 22 3  1  12 16 8  
Boat 3: 10 11 19 15 2  9  
Boat 4: 4  18 17 14 6  7  

Day 6
Boat 1: 1  4  18 8  9  21 
Boat 2: 11 17 3  5  24 15 
Boat 3: 19 22 20 13 2  7  
Boat 4: 14 6  16 12 10 23

Here is the "proof", outlining in which day and boat each pair of members meet:

1 and 2 meet on day 4  on boat 4
1 and 3 meet on day 5  on boat 2
1 and 4 meet on day 6  on boat 1
1 and 5 meet on day 1  on boat 3
1 and 6 meet on day 4  on boat 4
1 and 7 meet on day 3  on boat 3
1 and 8 meet on day 6  on boat 1
1 and 9 meet on day 6  on boat 1
1 and 10 meet on day 2  on boat 3
1 and 11 meet on day 3  on boat 3
1 and 12 meet on day 5  on boat 2
1 and 13 meet on day 1  on boat 3
1 and 14 meet on day 1  on boat 3
1 and 15 meet on day 3  on boat 3
1 and 16 meet on day 5  on boat 2
1 and 17 meet on day 4  on boat 4
1 and 18 meet on day 6  on boat 1
1 and 19 meet on day 4  on boat 4
1 and 20 meet on day 1  on boat 3
1 and 21 meet on day 6  on boat 1
1 and 22 meet on day 5  on boat 2
1 and 23 meet on day 2  on boat 3
1 and 24 meet on day 1  on boat 3
2 and 3 meet on day 3  on boat 1
2 and 4 meet on day 1  on boat 4
2 and 5 meet on day 2  on boat 1
2 and 6 meet on day 4  on boat 4
2 and 7 meet on day 6  on boat 3
2 and 8 meet on day 3  on boat 1
2 and 9 meet on day 5  on boat 3
2 and 10 meet on day 5  on boat 3
2 and 11 meet on day 5  on boat 3
2 and 12 meet on day 1  on boat 4
2 and 13 meet on day 6  on boat 3
2 and 14 meet on day 3  on boat 1
2 and 15 meet on day 5  on boat 3
2 and 16 meet on day 2  on boat 1
2 and 17 meet on day 4  on boat 4
2 and 18 meet on day 2  on boat 1
2 and 19 meet on day 6  on boat 3
2 and 20 meet on day 6  on boat 3
2 and 21 meet on day 4  on boat 4
2 and 22 meet on day 6  on boat 3
2 and 23 meet on day 3  on boat 1
2 and 24 meet on day 2  on boat 1
3 and 4 meet on day 4  on boat 2
3 and 5 meet on day 6  on boat 2
3 and 6 meet on day 1  on boat 1
3 and 7 meet on day 2  on boat 2
3 and 8 meet on day 5  on boat 2
3 and 9 meet on day 4  on boat 2
3 and 10 meet on day 1  on boat 1
3 and 11 meet on day 6  on boat 2
3 and 12 meet on day 5  on boat 2
3 and 13 meet on day 4  on boat 2
3 and 14 meet on day 3  on boat 1
3 and 15 meet on day 6  on boat 2
3 and 16 meet on day 5  on boat 2
3 and 17 meet on day 6  on boat 2
3 and 18 meet on day 1  on boat 1
3 and 19 meet on day 3  on boat 1
3 and 20 meet on day 4  on boat 2
3 and 21 meet on day 2  on boat 2
3 and 22 meet on day 5  on boat 2
3 and 23 meet on day 3  on boat 1
3 and 24 meet on day 6  on boat 2
4 and 5 meet on day 3  on boat 4
4 and 6 meet on day 5  on boat 4
4 and 7 meet on day 5  on boat 4
4 and 8 meet on day 6  on boat 1
4 and 9 meet on day 6  on boat 1
4 and 10 meet on day 2  on boat 3
4 and 11 meet on day 1  on boat 4
4 and 12 meet on day 1  on boat 4
4 and 13 meet on day 4  on boat 2
4 and 14 meet on day 5  on boat 4
4 and 15 meet on day 1  on boat 4
4 and 16 meet on day 4  on boat 2
4 and 17 meet on day 5  on boat 4
4 and 18 meet on day 6  on boat 1
4 and 19 meet on day 1  on boat 4
4 and 20 meet on day 4  on boat 2
4 and 21 meet on day 6  on boat 1
4 and 22 meet on day 3  on boat 4
4 and 23 meet on day 2  on boat 3
4 and 24 meet on day 3  on boat 4
5 and 6 meet on day 3  on boat 4
5 and 7 meet on day 4  on boat 1
5 and 8 meet on day 4  on boat 1
5 and 9 meet on day 3  on boat 4
5 and 10 meet on day 4  on boat 1
5 and 11 meet on day 6  on boat 2
5 and 12 meet on day 4  on boat 1
5 and 13 meet on day 5  on boat 1
5 and 14 meet on day 1  on boat 3
5 and 15 meet on day 6  on boat 2
5 and 16 meet on day 2  on boat 1
5 and 17 meet on day 6  on boat 2
5 and 18 meet on day 2  on boat 1
5 and 19 meet on day 2  on boat 1
5 and 20 meet on day 5  on boat 1
5 and 21 meet on day 5  on boat 1
5 and 22 meet on day 3  on boat 4
5 and 23 meet on day 5  on boat 1
5 and 24 meet on day 6  on boat 2
6 and 7 meet on day 5  on boat 4
6 and 8 meet on day 2  on boat 4
6 and 9 meet on day 3  on boat 4
6 and 10 meet on day 6  on boat 4
6 and 11 meet on day 2  on boat 4
6 and 12 meet on day 6  on boat 4
6 and 13 meet on day 2  on boat 4
6 and 14 meet on day 6  on boat 4
6 and 15 meet on day 2  on boat 4
6 and 16 meet on day 6  on boat 4
6 and 17 meet on day 5  on boat 4
6 and 18 meet on day 5  on boat 4
6 and 19 meet on day 4  on boat 4
6 and 20 meet on day 2  on boat 4
6 and 21 meet on day 4  on boat 4
6 and 22 meet on day 3  on boat 4
6 and 23 meet on day 6  on boat 4
6 and 24 meet on day 3  on boat 4
7 and 8 meet on day 4  on boat 1
7 and 9 meet on day 2  on boat 2
7 and 10 meet on day 4  on boat 1
7 and 11 meet on day 3  on boat 3
7 and 12 meet on day 4  on boat 1
7 and 13 meet on day 6  on boat 3
7 and 14 meet on day 5  on boat 4
7 and 15 meet on day 3  on boat 3
7 and 16 meet on day 3  on boat 3
7 and 17 meet on day 5  on boat 4
7 and 18 meet on day 5  on boat 4
7 and 19 meet on day 6  on boat 3
7 and 20 meet on day 6  on boat 3
7 and 21 meet on day 3  on boat 3
7 and 22 meet on day 6  on boat 3
7 and 23 meet on day 1  on boat 2
7 and 24 meet on day 4  on boat 1
8 and 9 meet on day 6  on boat 1
8 and 10 meet on day 4  on boat 1
8 and 11 meet on day 2  on boat 4
8 and 12 meet on day 5  on boat 2
8 and 13 meet on day 2  on boat 4
8 and 14 meet on day 3  on boat 1
8 and 15 meet on day 2  on boat 4
8 and 16 meet on day 5  on boat 2
8 and 17 meet on day 1  on boat 2
8 and 18 meet on day 6  on boat 1
8 and 19 meet on day 3  on boat 1
8 and 20 meet on day 2  on boat 4
8 and 21 meet on day 6  on boat 1
8 and 22 meet on day 5  on boat 2
8 and 23 meet on day 3  on boat 1
8 and 24 meet on day 4  on boat 1
9 and 10 meet on day 5  on boat 3
9 and 11 meet on day 5  on boat 3
9 and 12 meet on day 2  on boat 2
9 and 13 meet on day 4  on boat 2
9 and 14 meet on day 2  on boat 2
9 and 15 meet on day 5  on boat 3
9 and 16 meet on day 4  on boat 2
9 and 17 meet on day 1  on boat 2
9 and 18 meet on day 6  on boat 1
9 and 19 meet on day 5  on boat 3
9 and 20 meet on day 4  on boat 2
9 and 21 meet on day 6  on boat 1
9 and 22 meet on day 3  on boat 4
9 and 23 meet on day 1  on boat 2
9 and 24 meet on day 3  on boat 4
10 and 11 meet on day 5  on boat 3
10 and 12 meet on day 6  on boat 4
10 and 13 meet on day 3  on boat 2
10 and 14 meet on day 6  on boat 4
10 and 15 meet on day 5  on boat 3
10 and 16 meet on day 6  on boat 4
10 and 17 meet on day 3  on boat 2
10 and 18 meet on day 3  on boat 2
10 and 19 meet on day 5  on boat 3
10 and 20 meet on day 3  on boat 2
10 and 21 meet on day 1  on boat 1
10 and 22 meet on day 2  on boat 3
10 and 23 meet on day 6  on boat 4
10 and 24 meet on day 4  on boat 1
11 and 12 meet on day 1  on boat 4
11 and 13 meet on day 2  on boat 4
11 and 14 meet on day 4  on boat 3
11 and 15 meet on day 6  on boat 2
11 and 16 meet on day 3  on boat 3
11 and 17 meet on day 6  on boat 2
11 and 18 meet on day 4  on boat 3
11 and 19 meet on day 5  on boat 3
11 and 20 meet on day 2  on boat 4
11 and 21 meet on day 3  on boat 3
11 and 22 meet on day 4  on boat 3
11 and 23 meet on day 4  on boat 3
11 and 24 meet on day 6  on boat 2
12 and 13 meet on day 3  on boat 2
12 and 14 meet on day 6  on boat 4
12 and 15 meet on day 1  on boat 4
12 and 16 meet on day 6  on boat 4
12 and 17 meet on day 3  on boat 2
12 and 18 meet on day 3  on boat 2
12 and 19 meet on day 1  on boat 4
12 and 20 meet on day 3  on boat 2
12 and 21 meet on day 2  on boat 2
12 and 22 meet on day 5  on boat 2
12 and 23 meet on day 6  on boat 4
12 and 24 meet on day 4  on boat 1
13 and 14 meet on day 1  on boat 3
13 and 15 meet on day 2  on boat 4
13 and 16 meet on day 4  on boat 2
13 and 17 meet on day 3  on boat 2
13 and 18 meet on day 3  on boat 2
13 and 19 meet on day 6  on boat 3
13 and 20 meet on day 6  on boat 3
13 and 21 meet on day 5  on boat 1
13 and 22 meet on day 6  on boat 3
13 and 23 meet on day 5  on boat 1
13 and 24 meet on day 5  on boat 1
14 and 15 meet on day 4  on boat 3
14 and 16 meet on day 6  on boat 4
14 and 17 meet on day 5  on boat 4
14 and 18 meet on day 5  on boat 4
14 and 19 meet on day 3  on boat 1
14 and 20 meet on day 1  on boat 3
14 and 21 meet on day 2  on boat 2
14 and 22 meet on day 4  on boat 3
14 and 23 meet on day 6  on boat 4
14 and 24 meet on day 1  on boat 3
15 and 16 meet on day 3  on boat 3
15 and 17 meet on day 6  on boat 2
15 and 18 meet on day 4  on boat 3
15 and 19 meet on day 5  on boat 3
15 and 20 meet on day 2  on boat 4
15 and 21 meet on day 3  on boat 3
15 and 22 meet on day 4  on boat 3
15 and 23 meet on day 4  on boat 3
15 and 24 meet on day 6  on boat 2
16 and 17 meet on day 1  on boat 2
16 and 18 meet on day 2  on boat 1
16 and 19 meet on day 2  on boat 1
16 and 20 meet on day 4  on boat 2
16 and 21 meet on day 3  on boat 3
16 and 22 meet on day 5  on boat 2
16 and 23 meet on day 6  on boat 4
16 and 24 meet on day 2  on boat 1
17 and 18 meet on day 5  on boat 4
17 and 19 meet on day 4  on boat 4
17 and 20 meet on day 3  on boat 2
17 and 21 meet on day 4  on boat 4
17 and 22 meet on day 2  on boat 3
17 and 23 meet on day 2  on boat 3
17 and 24 meet on day 6  on boat 2
18 and 19 meet on day 2  on boat 1
18 and 20 meet on day 3  on boat 2
18 and 21 meet on day 6  on boat 1
18 and 22 meet on day 4  on boat 3
18 and 23 meet on day 4  on boat 3
18 and 24 meet on day 2  on boat 1
19 and 20 meet on day 6  on boat 3
19 and 21 meet on day 4  on boat 4
19 and 22 meet on day 6  on boat 3
19 and 23 meet on day 3  on boat 1
19 and 24 meet on day 2  on boat 1
20 and 21 meet on day 5  on boat 1
20 and 22 meet on day 6  on boat 3
20 and 23 meet on day 5  on boat 1
20 and 24 meet on day 5  on boat 1
21 and 22 meet on day 1  on boat 1
21 and 23 meet on day 5  on boat 1
21 and 24 meet on day 5  on boat 1
22 and 23 meet on day 4  on boat 3
22 and 24 meet on day 3  on boat 4
23 and 24 meet on day 5  on boat 1

Here's the C++ code I used:

#include <bits/stdc++.h>
using namespace std;

// Random Number Generation {{{
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) { return rng() % (r-l+1) + l; }
//}}}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  const int N = 24;
  const int B = 4;
  const int per_b = N/B;
  const int D = 6;

  vector A(D, vector<int>(N));
  for (auto &d : A) {
    iota(begin(d), end(d), 0LL);
    shuffle(begin(d), end(d), rng);
  }

  int cur_score = 0;
  vector meets(N, vector<int>(N));
  for (auto const& d : A) {
    for (int bi = 0; bi < B; bi++) {
      for (int i = bi*per_b; i < (bi+1)*per_b; i++) {
        for (int j = i+1; j < (bi+1)*per_b; j++) {
          auto [a, b] = minmax(d[i], d[j]);
          cur_score -= !!meets[a][b];
          meets[a][b]++;
          cur_score += !!meets[a][b];
        }
      }
    }
  }

  auto add_person = [&](int di, int bi, int pi, int delta) {
    auto const& d = A[di];
    int pi_idx = bi*per_b + pi;
    for (int i = bi*per_b; i < (bi+1)*per_b; i++) {
      if (i == pi_idx) continue;
      auto [a, b] = minmax(d[pi_idx], d[i]);
      cur_score -= !!meets[a][b];
      meets[a][b] += delta;
      cur_score += !!meets[a][b];
    }
  };

  // Needs bi != bj
  auto swap_people = [&](int di, int bi, int bj, int pi, int pj) {
    add_person(di, bi, pi, -1);
    add_person(di, bj, pj, -1);

    int pi_idx = bi*per_b + pi;
    int pj_idx = bj*per_b + pj;

    swap(A[di][pi_idx], A[di][pj_idx]);

    add_person(di, bi, pi, +1);
    add_person(di, bj, pj, +1);
  };

  auto score_brute = [&]() {
    vector<vector<bool>> ok(N, vector<bool>(N));
    for (auto &d : meets) fill(begin(d), end(d), 0);
    cur_score = 0;
    for (auto const& d : A) {
      for (int bi = 0; bi < B; bi++) {
        for (int i = bi*per_b; i < (bi+1)*per_b; i++) {
          for (int j = i+1; j < (bi+1)*per_b; j++) {
            auto [a, b] = minmax(d[i], d[j]);
            ok[a][b] = true;
            meets[a][b]++;
          }
        }
      }
    }
    int sum = 0;
    for (auto const& oki : ok) {
      sum += accumulate(begin(oki), end(oki), 0LL);
    }
    cur_score = sum;
    return sum;
  };

  for (int it = 0; it < 100'000'000; it++) {
    int di = randint(0, D-1);
    int bi = randint(0, B-2);
    int bj = randint(bi+1, B-1);

    int pi = randint(0, per_b-1);
    int pj = randint(0, per_b-1);

    int before = cur_score;
    swap_people(di, bi, bj, pi, pj);

    if (before > cur_score) {
      swap_people(di, bi, bj, pi, pj);
    }

    if (cur_score == N*(N-1)/2) break;

    if (it % 100000 == 0) {
      cout << "Checkpoint   " << it << ' ' << cur_score << endl;
      shuffle(begin(A[di]), end(A[di]), rng);
      score_brute();
      cout << "AfterShuffle " << it << ' ' << cur_score << endl;
    }
  }

  if (cur_score != N*(N-1)/2) cout << "Solution not found!" << endl, exit(0);

  for (int di = 0; di < D; di++) {
    cout << "Day " << di+1 << endl;
    for (int bi = 0; bi < B; bi++) {
      cout << "Boat " << bi+1 << ": ";
      for (int i = per_b*bi; i < per_b*(bi+1); i++) {
        cout << A[di][i]+1 << ' ';
        if (A[di][i]+1 < 10) cout << ' ';
      }
      cout << endl;
    }
    cout << endl;
  }
}
Edit Report
Pub: 16 Sep 2024 19:12 UTC
Edit: 16 Sep 2024 19:38 UTC
Views: 214