Array of integers

Probability Level 3

A $1000\times1000$ array is to be filled with integers between 1 and 1000 inclusive, with each integer appearing 1000 times. What is the maximum value of $n$ such that there necessarily exists a row or column with at least $n$ distinct integers?

The answer is 32.

2 solutions

Canwen Jiao
Jun 27, 2018

To minimize the number of different integers in the same row or column, we need to cluster each integer as much as possible, trying to put all 1's inside a square, and same for the one thousand 2's and so on. For example, we can put the 1's into a $31 \times 32$ almost-square with $8$ 1's remaining, and place these on the upper-left corner of the 1000 by 1000 grid. In the end, the 1000 by 1000 grid will be partitioned into 1000 smaller near-square sections, and each row or column will have at most 32 different numbers.

In question, max value of n is asked. I am thinking that in a row each integer can be distinct, so n = 1000. what am I doing wrong here???

Venkatesh Pagadala - 2 years ago

It’s a bit hard to understand by the wording of the question, but the question is really asking for the smallest numbers of distinct numbers on any given row, not the largest. Otherwise you’d be correct with 1000.

Philip Suskin - 1 year, 9 months ago

Rafay Ashary
Apr 23, 2017

Solution of a similar problem can be found here ; the method is not different.

I know the solution must be greater than 31 but i am not sure the correct answer is 32. I think the correct solution is 33. (200/50) 1+(200/40) 1+(200/25) 3=33 (Rows) (200/20) 1+(200/25) 1+(200/40) 3=33(Columns)

saurav shakya - 3 years, 3 months ago

Rafay Ashary, the solution you linked proves that the answer must be at least 1000^1/2 rounded up to the nearest integer - i.e. 32. However, this problem asks for a maximum value, so we would also need to prove that there exists a numbering scheme in which no row or column has more than 32 different integers. If anyone here can demonstrate the existence of such a scheme I would much appreciate it - and be much surprised, as I believe Saurav Shakya's answer (33) is correct. Saurav's scheme, as I understand it, breaks the 1000x1000 square into 200x200 squares, then subdivides 5 of those into 50x20 rectangles, 5 into 40x25 rectangles, and 15 into 25x40 rectangles. These 200x200 squares are arranged such that there is one tiled 50x20, one tiled 40x25, and three tiled 25x40 in each row and column. Every rectangle is filled with one particular integer. As a result, every row and every column has exactly 33 different integers. Thus, it does not seem possible to come up with any numbering scheme in which the max would be less than 33. (I have to admit I find this solution very clever. The best I initially came up with was tiling with 40x25s and 25x40s, which had a max of 34. Canwen Jiao, I also tried the 32x31 near-squares scheme, but the extra 8 numbers on the side increased the max row or column count above 32.)

Morgan Makhina - 2 years, 9 months ago

I agree with this. As Saurav's solution has 33 distinct numbers in ANY row and ANY column, it seems ultimately optimised, and pretty unlikely to find a counter example for 33. Untill a counter example can be found, 33 seems to be the solution. The solution proposed by Jiao doesn't seem convincing, especially as his conclusion "each row or column will have at most 32 different number" is not correct (in his setup).

Wouter Dobbelaere - 7 months, 1 week ago

Array of integers

The answer is 32.

2 solutions

0 pending reports