March 2004
<<February March April>>
This month's puzzle comes from Yuval Dekel, based on work by Vladeta Jovovic and Vladimir Baltic.
A sequence of integers is "weakly monotone" if it is either non-decreasing or non-increasing. For example, there are exactly six weakly monotone sequences of length 3 whose elements are chosen from {0,1}, namely 000, 001, 011, 100, 110, 111.
The sequence 010 fails to be weakly monotone because it is not non-decreasing (a_2 > a_3) nor non-increasing (a_1 < a_2).
An M by N array of integers is "valid" if each of its rows and columns is weakly monotone.
Part 1:
Give, with proof, a formula (in terms of M and N) for the number of valid M by N arrays, with elements chosen from {0,1}.
Part 2:
Give, with proof, a formula (in terms of N) for the number of valid 3 by N arrays, with elements chosen from {0,1,2}.
Part 3:
Give, with proof, a formula (in terms of M and N) for the number of valid M by N arrays, with elements chosen from {0,1,2}.
Part 4:
Give, with proof, a formula (in terms of M, N and K) for the number of valid M by N by K arrays, with elements chosen from {0,1}.
(Here "valid" means that each line, in each of the three principal directions, is weakly monotone.)
We will accept submissions that solve (with proof) at least one part. Preference is given to closed-form solutions (no recursion, no sums, just binomial coefficients). Each proof is expected to be your own; it's no fair using a proof that you've seen elsewhere.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
03/01/2004 @ 9:30 AM ET
Solution:
04/01/2004 @ 8:30 AM ET
List Updated:
04/01/2004 @ 8:30 PM ET
People who answered correctly:
Gyozo Nagy: 1,2,3 (3.2.2004 @08:17:23 AM EDT)
Narayanan Rajamani: 1 (3.2.2004 @11:15:14 PM EDT)
Rustam Miftakhutdinov: 1 (3.3.2004 @03:00:52 AM EDT)
Kalyana Chakravarthy: 1 (3.3.2004 @03:04:57 PM EDT)
David Woodruff: 1 (3.4.2004 @11:09:07 PM EDT)
Yeqi: 1 (3.6.2004 @06:47:35 AM EDT)
Vladimir Sedach: 1 (3.7.2004 @03:59:17 PM EDT)
Coserea Gheorghe: 1 (3.8.2004 @03:57:27 AM EDT)
Luke Pebody: 1 (3.8.2004 @05:16:56 AM EDT)
M Venkata Ramayya: 1 (3.9.2004 @12:08:31 AM EDT)
Scott Hotes: 1 (3.9.2004 @03:26:42 AM EDT)
Kalyana Chakravarthy: 2,3 (3.9.2004 @07:34:31 AM EDT)
Aleksey Pinkin: 1 (3.10.2004 @02:33:00 PM EDT)
John G Fletcher: 1 (3.10.2004 @07:38:58 PM EDT)
Clive Tong: 1 (3.15.2004 @06:48:01 AM EDT)
Tim Paulden: 1 (3.17.2004 @06:42:49 AM EDT)
Gyozo Nagy: 4 (3.16.2004 @05:21:09 PM EDT)
R. Nandakumar: 1 (3.17.2004 @11:18:00 PM EDT)
Daniel Bitin: 1 (3.22.2004 @12:58:28 PM EDT)
Andre Rzym: 1 (3.23.2004 @04:10:55 PM EDT)
John G. Fletcher: 2 (3.23.2004 @11:43:50 PM EDT)
M Venkata Ramayya: 2,3 (3.25.2004 @01:34:47 AM EDT)
Derek Kisman: 1,2 (3.25.2004 @11:23:30 AM EDT)
Samuel Hargestam: 1 (3.28.2004 @06:41:38 PM EDT)
Sorin Ostafiev: 1 (3.29.2004 @05:58:37 AM EDT)
Vincent Vermaut: 1 (3.30.2004 @07:43:48 AM EDT)
IQSTAR: 1 (3.30.2004 @12:39:55 PM EDT)
Dan Dima: 1 (3.31.2004 @12:22:25 PM EDT)
Arun Sivaramakrishnan: 1 (3.31.2004 @12:43:47 PM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.