Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 6.2 National olympiad Find the answer

A k×kk \times k array contains each of the numbers 1,2,,m1, 2, \dots, m exactly once, with the remaining entries all zero. Suppose that all the row sums and column sums are equal. What is the smallest possible value of mm if k=3nk = 3^n (nN+n \in \mathbb{N}^+)?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider a k×k k \times k array, where k=3n k = 3^n for a positive integer n n . The array contains each of the integers 1,2,,m 1, 2, \ldots, m exactly once, and the remaining entries are all zeros. We are tasked with finding the smallest possible value of m m such that all row sums and column sums are equal.

In a k×k k \times k array with equal row and column sums S S , the total sum of the entries is k×S k \times S . Since the entries 1,2,,m 1, 2, \ldots, m appear exactly once, the total sum of non-zero entries is:

i=1mi=m(m+1)2 \sum_{i=1}^{m} i = \frac{m(m+1)}{2}

To satisfy that the row sums and column sums are equal, the non-zero entries must be distributed such that their sum for any row or column leads to an integer average. This implies:

k×S=m(m+1)2 k \times S = \frac{m(m+1)}{2}

Given that k=3n k = 3^n , we analyze how to distribute the integers optimally to achieve the same row and column sums. We focus on ensuring each sum is the same while minimizing m m .

Observing that the simplest scenario would involve filling entries up to the largest non-zero integer across rows or columns, we deduce that filling in consecutive numbers maximizes the use of non-zero entries uniformly across rows and columns:

Set m=3n+11 m = 3^{n+1} - 1 . This setting ensures that all m m non-zero numbers produce a sum that aligns with the requisite uniformity for both rows and columns:

- The total number of non-zero cells is m=3n+11 m = 3^{n+1} - 1 .
- This arises as the maximum integer sum obtainable for completed non-zero fills which ensures all sums equate.

Through careful arrangement, we achieve consistent row and column summations with the structure:
m=3n+11 m = 3^{n+1} - 1

Thus, the smallest possible value of m m is:
3n+11 \boxed{3^{n+1} - 1}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.