數學營有8個小隊，有5個大地遊戲要玩，每個大地遊戲由2個小隊互相對抗
假設每個遊戲花的時間都一樣是T，那麼在同一個時間內可以進行4個遊戲，而且只要5T的時間就可以把整個流程走完
不過安排上有一些規則：
- 同一個遊戲，每小隊都要恰好玩一次
- 同一個時間內，每小隊都要恰好玩一個遊戲(雖然是廢話，不過還是個重要的條件)
- 對抗過的兩小隊，不要再對抗第二次
學姐的安排模式是這樣的：
ABCDE表示5個不同的遊戲，T1~T5表示5個時間T，1~8表示第1~第8小隊
作表格如下
| A | B | C | D | E | |
| T1 | X | 12 | 34 | 56 | 78 |
| T2 | X | ||||
| T3 | X | ||||
| T4 | X | ||||
| T5 | X |
為了簡化討論，我們可以不考慮對角線
每個格子裡面放2個小隊，如以上範例
此時安排就比較能找規律了，3個規則也等價於：
- 每個數字在每一直行恰出現一次
- 每個數字在每一橫列恰出現一次
- 每個格子包含的數對只能出現一次
我和其他人也是不管怎麼安排，就是會因為規則限制而排不出來
這時候我當然就萌生了一個想法：該不會這個問題無解吧
要證明這題無解，我目前還沒想到方法，不過倒是想嘗試看看寫程式下去跑窮舉
於是決定用MATLAB寫底稿
因為矩陣每一格只能放一個元素，但是這個表格每一格都要放一組數對，所以我想到了一個解決辦法，那就是「質因數法」
現在我們不使用[1 2 3 4 5 6 7 8]代表各小隊，我們改用[2 3 5 7 11 13 17 19]這8個質數
原先的對抗組合，例如第2和第6小隊原本記為(2,6)，現在記為3*13=39(第2和第6個質數)
於是上面3個規則又有等價的敘述了：
- 每一直行的數字兩兩互質
- 每一橫列的數字兩兩互質
- 每個格子所裝的數字都不相同
| A | B | C | D | E | |
| T1 | X | 6 | 35 | 143 | 323 |
| T2 | X | ||||
| T3 | X | ||||
| T4 | X | ||||
| T5 | X |
現在寫程式的思維是這個樣子的：
我們先製造所有可能的組合，共有C(8,2)=28種，舉例來說，數對記法就是(1,2) (1,3) (1,4) ... (7,8)，質因數法就是2*3=6、2*5=10、2*7=14、...、17*19=323
因為我們將使用質因數法作為此程式的main idea，所以將這28個數字由小排到大，令為w向量，則w=[6 10 14 15 21 ...... 323]
由於規則1和2需要用到互質的條件，現在要建立一個全部元素為1的5*5矩陣，如此一來，接下來的判定基本上就沒什麼問題了
再來是放置數字的規則(註：MATLAB的矩陣是column major，因此A(9)是代表a_42元素)
如果遇到w(k)不符合規則時，則換放入w(k+1)
由A(2)開始放入w(1)，再來移動到A(3)，由w(1)開始嘗試，因為w(1)上一格放過了，違反規則，因此換成w(2)。如此不斷的進行檢查再放入
如果一直換到w(28)都不符合規則時，將數字改回1，檢討上一格A(i-1)的數字，若上一格放入w(m)，則改為w(m+1)，再移回來A(i)，從w(1)開始再試一遍，試到數字放得進去為止
如此不斷重複，直到試出來或是跑完所有可能仍無解為止
於是，MATLAB表示：無解
一開始在猜測有沒有解的時候，有考慮過6個小隊玩4種遊戲的情況，結果一下子就被我排出解來了。另外，4個小隊玩3個遊戲也很容易就發現無解
這是6個小隊要玩4種遊戲的情況(底稿)
v = [2 3 5 7 11 13]; %六個質因數代表六小隊
%把這六個質因數兩兩相乘的組合全部列出來
p = v'*v;
for i = 1:6
for j = 1:6
if (i>=j)
p(i,j) = 0; %把重複的數字去掉
end
end
end
%把這些組合排成列向量w，並去掉0
for i = 1:36
w(i) = p(i);
end
w = sort(w);
w([1:21]) = [];
A = ones(4,4); %建立4*4表格放入數字
i = 1; %A矩陣的位置(column major)，例如A(7)即為第3列第2行的元素
while i<16
if (mod(i,5)==1), i = i + 1; end %逢對角線即跳至下一個數(為了簡化討論，不將元素放至對角線)
I = i - 4*ceil(i/4) + 4; %將i轉換為第I列第J行
J = ceil(i/4);
k = 1; %w(k)即為w向量中第k個元素
while k<=15
%判定若將w(k)放入A(I,J)，是否會與同一列、同一行其他數互質，以及是否重複選取A(i)以前的元素
if (prod(gcd(A(I,:),w(k)))==1 && prod(gcd(A(:,J),w(k)))==1 && sum(sum(A==w(k)))==0)
%符合條件者就放入表格中，並且準備判定下一個
A(i) = w(k);
if (mod(i,5)==0) %跳過對角線
i = i + 2;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
else
i = i + 1;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
end
break;
else
k = k + 1; %不符合條件就換w(k+1)，並且再執行一次上面的判定
end
while (k==16) %當所有w(k)都試過一遍卻沒有符合的條件，就把這一格改成1，並且回頭將上一格的w(k)改成w(k+1)
A(i) = 1;
if (mod(i,5)==2)
i = i - 2;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
else
i = i - 1;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
end
if (i==0), break; end %所有可能都試過了，但是都不符合條件，才會退到i=0。此時跳出所有迴圈，並宣布"No solution."
k = find(A(i)==w) + 1;
end
if (i==0), break; end
end
if (i==0), disp('No solution.'); break; end
if (i>=16), disp(A); end %所有數字都排進去，並且都符合規則，就把結果列出來，並結束迴圈
end
這是n個小隊要玩n/2+1種遊戲的情況(函數)
function out = team(n)
p = 2; s = 1; v = []; m = n/2 + 1;
while s<=n
if isprime(p)==1
v = [v p];
s = s + 1;
end
p = p + 1;
end
P = v'*v;
for i = 1:n
for j = 1:n
if (i>=j)
P(i,j) = 0;
end
end
end
for i = 1:n^2
w(i) = P(i);
end
w = sort(w);
w([1:n*(n+1)/2]) = [];
A = ones(m);
i = 1;
while i<m^2
if (mod(i,m+1)==1), i = i + 1; end
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
k = 1;
while k<=n*(n-1)/2
if (prod(gcd(A(I,:),w(k)))==1 && prod(gcd(A(:,J),w(k)))==1 && sum(sum(A==w(k)))==0)
A(i) = w(k)
if (mod(i,m+1)==0)
i = i + 2;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
else
i = i + 1;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
end
break;
else
k = k + 1;
end
while (k>n*(n-1)/2)
A(i) = 1
if (mod(i,m+1)==2)
i = i - 2;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
else
i = i - 1;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
end
if (i==0), break; end
k = find(A(i)==w) + 1;
end
if (i==0), break; end
end
if (i==0), disp('No solution.'); break; end
if (i>=m^2), disp(A); end
end
