在不改變任何行或列的總和的情況下製作矩陣的倍數的元素

Question

我偶然發現了這個有趣的問題：https://prologin.org/train/2016/semifinal/42_le_retour（法語）。

總之，我們給予

40 0 2 
0 84 0 
2 42 40 

目的是修改元素這個矩陣，使他們都整除42隨機數組成的矩陣，即：;然而，任何行和列的總和應保持與任何修改之前的相同。 （原來的問題是計算所需的最小點擊次數，假設每次點擊加或減1）

我想知道是否和爲什麼這總是可能的。

Answer 1

在3×3矩陣的可能動作是：

1. • 添加+ -1到拐角值
   • 添加+ -1到相對的角落
   • 加入 - + 1至相鄰角落

2.

• 添加+ -1到拐角值
• 加入 - + 1到鄰居值
• 添加+ -1到中間值

第一種可能性具有兩個變體，區別僅在標誌。第二種可能性總共有8個變體（四個不同的角和不同的尺寸）。

我不知道這是否總是可行的，特別是因爲我們不知道矩陣的極限並且根本不清楚我們是否有方矩陣。但是，您可以使用回溯來檢查這一點。無論何時你到達一個矩陣，其中每個元素的模42與最初相同，你需要追溯，直到找到解決方案。