Warmup question:
Using all the numbers 1, 2, 3, ... 15, each exactly once, can you construct a matrix with 5 rows and 3 columns such that all the row sums are equal?
Main question:
Using all the numbers 1, 2, 3, ... 15, each exactly once, can you construct a matrix with 5 rows and 3 columns such that all the row sums are equal AND all the column sums are equal?
Partial answers are welcome!
Here is a grid that does both:
I used trial and error, but there was a key insight that made it fairly trivial:
The eight odd numbers must be in 4 pairs of 2 along the rows, or the sum of the row with the odd number will be odd- and the magic number along the rows must be 24. Similarly, it was important to ensure an even number of odd numbers along each column; my solution had 2, 4, 2, but 4, 4, 0 may be possible as well.
The other kind of solution, hinted at by @ilikecorgis:
$\begin{array}{ccccc}1&3&7&15&14\\13&9&11&5&2\\10&12&6&4&8\end{array}$
You can find all the possible combinations using the Python script:
itertools import permutations
from pprint import pprint
from typing import Generator
def permutations_with_remaining(
items: tuple[int, ...],
indexes: tuple[int, ...],
n: int,
total: int,
) -> Generator[tuple[tuple[int, ...], tuple[int, ...], tuple[int, ...]], None, None]:
"""Pick any n of the items that sum to the given total.
Args:
items: The items to pick from.
indexes: The indexes to pick from.
n: The number of items to pick.
total: The expected total for the picked items.
Yields:
Three tuples representing the picked values, picked indexes (in the order
corresponding to the picked values), and unpicked indexes (in their original
order).
"""
for picked_indexes in permutations(indexes, n):
picked = tuple(items[i] for i in picked_indexes)
if sum(picked) != total:
continue
unpicked_indexes = tuple(i for i in indexes if i not in picked_indexes)
yield picked, picked_indexes, unpicked_indexes
def valid_ordered_first_row(
indexes: tuple[int, ...],
) -> bool:
"""Whether the items in the first row are valid and ordered.
Args:
indexes: The indexes to of the items in the first row.
Returns:
True if the the first row contains the initial index and if all the
indexes are ordered.
"""
return (
indexes[0] == 0
and all(indexes[i] < indexes[i + 1] for i in range(len(indexes) - 1))
)
def magic_rectangles(
items: tuple[int, ...],
row_size: int,
ordered: bool = True,
) -> Generator[tuple[tuple[int, ...], ...], None, None]:
"""Find magic rectangles for the given items.
A megic rectangle arranges the items into a rectangular matrix, with the given row
size, where all the rows sum to the same value and all the columns sum to the same
value.
Args:
items: The items to arrange into magic rectangles.
row_size: The number of items in each row.
ordered: Whether to only output ordered magic rectangles (with the first item
in the top-left matrix cell and the top-row and left-column ordered) or to
output all permutations of magic rectangles.
Yields:
Each valid magic rectangle.
"""
column_size, column_rem = divmod(len(items), row_size)
assert column_rem == 0
row_total, row_rem = divmod(sum(items), column_size)
col_total, col_rem = divmod(sum(items), row_size)
assert row_rem == 0
assert col_rem == 0
row_indexes = []
row_values = []
row_stack = [
permutations_with_remaining(
items,
tuple(range(len(items))),
row_size,
row_total
),
]
while row_stack:
try:
row, picked_indexes, remaining_indexes = next(row_stack[-1])
if ordered and (
picked_indexes[0] < row_indexes[-1]
if row_values
else not valid_ordered_first_row(picked_indexes)
):
continue
if remaining_indexes:
row_indexes.append(picked_indexes[0])
row_values.append(row)
row_stack.append(
permutations_with_remaining(
items,
remaining_indexes,
row_size,
row_total,
),
)
else:
rows = (*row_values, row)
for column in zip(*rows):
if sum(column) != col_total:
break
else:
yield rows
except StopIteration:
_ = row_stack.pop()
if row_values:
_ = row_values.pop()
_ = row_indexes.pop()
solution = list(magic_rectangles(tuple(range(1, 5*3 + 1)), 3))
pprint(solution)
Which gives the output:
[((1, 8, 15), (2, 9, 13), (11, 10, 3), (12, 7, 5), (14, 6, 4)),
((1, 8, 15), (2, 13, 9), (11, 10, 3), (12, 5, 7), (14, 4, 6)),
((1, 8, 15), (3, 7, 14), (11, 9, 4), (12, 10, 2), (13, 6, 5)),
((1, 8, 15), (4, 14, 6), (10, 11, 3), (12, 5, 7), (13, 2, 9)),
((1, 8, 15), (5, 12, 7), (9, 13, 2), (11, 3, 10), (14, 4, 6)),
((1, 8, 15), (6, 13, 5), (9, 4, 11), (10, 12, 2), (14, 3, 7)),
((1, 8, 15), (7, 3, 14), (9, 11, 4), (10, 12, 2), (13, 6, 5)),
((1, 8, 15), (7, 14, 3), (9, 11, 4), (10, 2, 12), (13, 5, 6)),
((1, 9, 14), (3, 6, 15), (11, 8, 5), (12, 10, 2), (13, 7, 4)),
((1, 9, 14), (3, 8, 13), (10, 12, 2), (11, 6, 7), (15, 5, 4)),
((1, 9, 14), (3, 8, 13), (10, 12, 2), (11, 7, 6), (15, 4, 5)),
((1, 9, 14), (3, 11, 10), (8, 12, 4), (13, 6, 5), (15, 2, 7)),
((1, 9, 14), (4, 7, 13), (8, 11, 5), (12, 10, 2), (15, 3, 6)),
((1, 9, 14), (4, 13, 7), (8, 5, 11), (12, 10, 2), (15, 3, 6)),
((1, 9, 14), (5, 4, 15), (10, 12, 2), (11, 7, 6), (13, 8, 3)),
((1, 9, 14), (5, 11, 8), (7, 4, 13), (12, 10, 2), (15, 6, 3)),
((1, 9, 14), (5, 15, 4), (10, 2, 12), (11, 6, 7), (13, 8, 3)),
((1, 9, 14), (6, 3, 15), (8, 11, 5), (12, 10, 2), (13, 7, 4)),
((1, 9, 14), (6, 11, 7), (8, 3, 13), (10, 12, 2), (15, 5, 4)),
((1, 9, 14), (6, 11, 7), (8, 13, 3), (10, 2, 12), (15, 5, 4)),
((1, 10, 13), (2, 7, 15), (11, 8, 5), (12, 9, 3), (14, 6, 4)),
((1, 10, 13), (2, 15, 7), (11, 8, 5), (12, 3, 9), (14, 4, 6)),
((1, 10, 13), (3, 12, 9), (7, 6, 11), (14, 8, 2), (15, 4, 5)),
((1, 10, 13), (3, 12, 9), (7, 11, 6), (14, 2, 8), (15, 5, 4)),
((1, 10, 13), (4, 6, 14), (9, 12, 3), (11, 5, 8), (15, 7, 2)),
((1, 10, 13), (4, 14, 6), (8, 5, 11), (12, 9, 3), (15, 2, 7)),
((1, 10, 13), (4, 14, 6), (8, 11, 5), (12, 3, 9), (15, 2, 7)),
((1, 10, 13), (5, 4, 15), (9, 12, 3), (11, 6, 7), (14, 8, 2)),
((1, 10, 13), (7, 11, 6), (8, 2, 14), (9, 12, 3), (15, 5, 4)),
((1, 11, 12), (2, 14, 8), (9, 5, 10), (13, 4, 7), (15, 6, 3)),
((1, 11, 12), (2, 14, 8), (9, 5, 10), (13, 7, 4), (15, 3, 6)),
((1, 11, 12), (2, 15, 7), (10, 5, 9), (13, 3, 8), (14, 6, 4)),
((1, 11, 12), (3, 15, 6), (9, 5, 10), (13, 7, 4), (14, 2, 8)),
((1, 11, 12), (5, 10, 9), (6, 4, 14), (13, 8, 3), (15, 7, 2)),
((1, 11, 12), (5, 10, 9), (6, 14, 4), (13, 3, 8), (15, 2, 7)),
((1, 11, 12), (6, 4, 14), (8, 13, 3), (10, 5, 9), (15, 7, 2)),
((1, 11, 12), (6, 14, 4), (8, 3, 13), (10, 5, 9), (15, 7, 2)),
((1, 11, 12), (7, 4, 13), (8, 14, 2), (9, 5, 10), (15, 6, 3)),
((1, 11, 12), (7, 15, 2), (8, 3, 13), (10, 5, 9), (14, 6, 4))]
Finding all 39 unique solutions (eliminating duplicates that could be found by re-ordering the rows and columns).
If you want all possible permutations of magic rectangle then:
solution = list(magic_rectangles(tuple(range(1, 5*3 + 1)), 3, ordered=False))
Which will generate 28,080 magic rectangles ($28080 = 39 \times 3! \times 5!$, since there are $3!$ ways to re-order the 3 columns and $5!$ ways to re-order the 5 rows).
Another possibility.
$\begin{pmatrix}14&6&4\\7&15&2\\3&8&13\\5&10&9\\11&1&12\end{pmatrix}$
Where the sum of all rows is 24 and the sum of all columns is 40
Here's another:
| C1 | C2 | C3 |
|---|---|---|
| 12 | 10 | 2 |
| 7 | 11 | 6 |
| 8 | 13 | 3 |
| 9 | 1 | 14 |
| 4 | 5 | 15 |
