Problem of the Month (March 1999)

An average array is a rectangular array of positive integers so that: each number (except for the smallest and largest) is the average of the numbers in horizontally and vertically adjacent cells. To avoid trivialities, we require that not all the numbers are the same. For example, here is a 2x3 average array:

358
146

We are interested in how small the numbers in an average array can be. Specifically, what is the smallest possible value of the largest number in an average array of a given size? What if all the numbers have to be different? What if the average includes diagonally adjacent cells? What about larger dimensional arrays?

ANSWERS

Let C(m,n) be the minimum possible largest element in an mxn average array. We use a ''x'' subscript if the average includes diagonal cells, and we use a ''*'' superscript if all the cells must be different.

Clearly C(1,n)=Cx(1,n)=C*(1,n)=Cx*(1,n)=n, as the array (1 2 3 . . . n ) works.

Joseph DeVincentis noticed that Cx*(2,n) is undefined for n≥2, as there are no such arrays. Also, he showed that Cx(2,n)=3: one such array is filled with 2's except for one column which contains a 1 and a 3.

Brendan Owen wrote a computer program to generate average arrays. He generated all the data below.

He showed that Cx(n1, n2, . . . , 2)=3, and that C(n1, n2, . . .) and Cx(n1, n2, . . .) always exist. He also showed that Cx*(n1, n2, . . . , 2) doesn't exist. The only other known values which don't appear to exist are Cx*( . . .,3,3,3).

Here are some answers for small arrays:

C(m,n): Repetitions Allowed, No Diagonals

m \ n 2345678
2 34812194298
3 4514116327298
4 81411502816163215004
5 121150371245115939608
6 1963281612451437066874283746
7 4227163211597066838534667448
8 982981500439608742837464667448471247
9 154696937727562267721614331057338
10 10712212232445454134716123 146585277988513801295
11 572179198830752914522574 4061957558727863626
12 9346819851928121220082212839 140726299881157365463811298
13 21324674387446074351010388604 115245795 
14 53921893136296090181087528 3486066382721481359503 
15 3825122122205331225261 2227981245  

C*(m,n): Repetitions Not Allowed, No Diagonals

m \ n 234567
2 488261994
3 830742693563309
4 874629602816118668
5 2626996041755024276501
6 19356281655026085989568
7 9433091186684276501989568206991
8 9811178150045044650474283746236701922202
9 34810351339941892694437 547462302474044608301
10 1072802822324442601245 3471612327317507372
11 129651914120146471476429856053 1987654990611912444546191029
12 934565118519283914071518 8221283936025114345204896
13 48346511653165912842678122151013 756445450490241857217354169779821
14 5394798118136296090981143881088 34860663827334722240784573
15 1803833196432866207958176981282511 126494851419642 

Cx(m,n): Repetitions Allowed, Diagonals

m \ n 3456
3 76429643
4 64115124714774206
5 29124726189972
6 643147742068997252593
7 13596672551198206320
8 383213664495160899264066638865904
9 64337404525863126102324864
10 1366906347782194286418808411 141881269264428327946
11 3077723392673122211721307821730
12 32420934159327027119583278668008656 11208236199692349184890772
13 14739559583308466519711812108279351038
14 26058442588666921314287991886445877264 281486448978113626690459320
15 7061521643268270270864611476607238512548682

Cx*(m,n): Repetitions Not Allowed, Diagonals

m \ n345
3 61512503087
4 12505754353073
5 30873530732132027
6 8570214774206268488939
7 8322074614908701753185101
8 9644111366449511972426351
9 755168313023074315503443919804825
10 8775235263477821942866614878861143
11 22479876051213956876239936878438722065
12 321835513524159327027119583500316181326089640
13 6223446445631297850242543736908297069251057289337
14 721258992031588666921314287996347210584170775952
15 5649743662765128110275546239432420 2484311052067594484723

Cubes

sizeC( )C*( )Cx( ) Cx*( )
2×2 343-
2×2×2 6-3-
2×2×2×2 9-3-
2×2×2×2×2 33-3-
2×2×2×2×2×2 27-3-
3×3 5307615
3×3×3 17-119-
3×3×3×3 53-15691-
4×4 11621155754
4×4×4 66125569397618288736786773864239435495
5×5 376152612132027
5×5×5 2500910572852329  
6×6 14360855259334135139
7×7 38532069915090691311752974558260469
8×8 471247199490791970213363103551920949676

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 3/7/99.