2010年8月22日 星期日

Two Interesting Questions

It is a long while since I wrote here last time. I have been to Europe and visited the Deutsche Museum in Munich. There is a small corner about Mathematics there and I took some photos. Maybe I post it next time.

Recently I read two interesting questions. Let me share them here.

1)

Find a smallest finite set of integers, such that every integer in the set is the sum of two other distinct elements in the set. There is one another rule: if x is an element of the set, then -x must NOT be an element of the set.

2)

A square matrix is said to be doubly stochastic if the entries in each row and in each column sum to the same value.

A permutation matrix is a square matrix where each entry in the matrix is either 0 or 1, and there is one and only one entry in each row and in each column which is 1.

Prove that any doubly stochastic matrix is a convex linear combination of permutation matrices.

Comment: The first question is interesting by itself. The second question is considered interesting because an easy solution by induction is possible, after knowing a combinatorial theorem called Hall's Theorem. The question itself may mislead you to some linear algebra arguments.

2 則留言:

Simon 提到...

1.Empty Set :P

For non-empty one, let S be a set satisfying the condition. Obviously, 0 does not belong to S. By Well Ordering Property, there exists one smallest element a. By the definition of S, a=b+c for some distinct elements b and c of S. Since a is the smallest element of S, a<0 and also b=a-c<0 and c=a-b<0. Then there exist at least 3 negative elements in S.

Suppose S has exactly 3 negative elements. Then the three elements are namely a, b and c. WLOG, assume b < c < 0. There exist p and q in S such that b=p+q. Trivially, p < 0 or q < 0. WLOG, assume p < 0. We have p=a or p=b or p=c. Note b=a+(-c) and -c does not belong in S. p=/=a. Since 0 does not belong in S, p=/=b. As b < c, b-c < 0. b=c+r, where b < r < 0. The only element s in S satisfying b < s < 0 is c. So p=/=c. This leads to a contradiction.

Therefore, S has at least 4 negative elements. Analogously, S has at least 4 positive elements.

Suppose |S|=8. Let S = {a,b,c,d,e,f,g,h} with a is the smallest, h is the greatest, a=b+c, h=f+g, b < c, f < g, d < 0 end e > 0. Then from above arguments, b=d+x and g=e+y for some x,y in S.
Suppose x=c. c=b+(-d)=a+(-b) and the only element s in S satisfying c < s < 0 is d, contradiction. Thus, x=/=c.
Analogously, y=/=f. Hence x > 0 and y<0. Arranging the elements of S in ascending order: a,d,b,c,f,g,e,h.
a y > -f. So, c > -f, giving f > -c, a contradiction.
Thus, |S| > 8.

One such set is
{-10,-8,-6,-4,2,3,5,7,12}

Simon 提到...

Enabling HTML code makes some content disappeared

The last few lines should be
"Arranging the elements of S in ascending order: a,d,b,c,f,g,e,h.
a < d implies b+c < b-x and 0 < x < -c. So, f < -c. e < h implies g-y < f+g and 0 > y > -f. So, c > -f, giving f > -c, a contradiction."