Let $n$ be a positive integer. Denote $M = \{(x, y)|x, y \text{ are integers }, 1 \leq x, y \leq n\}$. Define function $f$ on $M$ with the following properties: a.) $f(x, y)$ takes non-negative integer value; b.) $\sum^n_{y=1} f(x, y) = n - 1$ for $1 \eq x \leq n$; c.) If $f(x_1, y_1)f(x2, y2) > 0$, then $(x_1 - x_2)(y_1 - y_2) \geq 0.$ Find $N(n)$, the number of functions $f$ that satisfy all the conditions. Give the explicit value of $N(4)$.
Problem
Source: China TST 2000, problem 6
Tags: function, LaTeX, algebra unsolved, algebra
Alexander Lenin
11.06.2005 05:38
I know that N(n)=(n^2-1)C(n-1) so N(4)=15C3=455 Because of my poor English and poor LaTex skills, I can't give the whole solution.
hxy
06.02.2010 12:37
Here is the official solution which is much more elegant than the previous one
Attachments:


P-H-David-Clarence
17.10.2016 13:29
Good solution!And I think we can use generating function too.