All questions

...
falcon handsome moderators
09/03/2017 at 12:43
Answers
6
Follow

Let \(a_0\)= 1, \(a_1\)=1 and \(a_n=4a_{n-1}-4a_{n-2}\) for n>=2

Find a formula for a\(_n\) in terms of n.

generating functions


...
falcon handsome moderators
09/03/2017 at 12:55
Answers
1
Follow

In each cell of a 100 x 100 table, one of the integers 1,2,...,5000 is written. Moreover, each integer appears in the table exactly twice. Prove that one can choose 100 cells in the satisfying three conditions below.

(1) Exactly one cell is chosen in each row.

(2) Exactly one cell is chosen in each column.

(3) The numbers in the cells chosen are pairwise distinct

probabilistic method

  • ...
    demo acc 10/03/2017 at 14:42

    very diffcult khocroioe


...
falcon handsome moderators
09/03/2017 at 12:58
Answers
3
Follow

Given 2n points in a plane with no three of them collinear. Show that thay can be divided into n pairs such that the n segments joining each pair do not intersect

games

  • ...
    Ace Legona 09/03/2017 at 19:14

    In the beginning randomly pair the points and join the segments. Let \(S \) be the sum of the lengths of the segments. (Note that since there are finitely many ways of connecting \(2n \) points by \(n \) segments, there are finitely many possible values of \(S\).) If two segments \(AB\)and \(CD\)intersect at \(O\), then replace pairs \(AB\)and \(CD\)by \(AC\)and \(BD\). Since

    \(AB + CD = AO + OB + CO + OD > AC + BD\)

    by the triangle inequality, whenever there is an intersection, doing this replacement will always decrease \(S\). Since there are only finitely many possible values of \(S\), so eventually there will not be any intersection.

  • ...
    Faded 19/01/2018 at 14:52

    In the beginning randomly pair the points and join the segments. Let S be the sum of the lengths of the segments. (Note that since there are finitely many ways of connecting 2n points by n segments, there are finitely many possible values of S.) If two segments ABand CDintersect at O, then replace pairs ABand CDby ACand BD

    . Since

    AB+CD=AO+OB+CO+OD>AC+BD

    by the triangle inequality, whenever there is an intersection, doing this replacement will always decrease S

    . Since there are only finitely many possible values of S, so eventually there will not be any intersection.

  • ...
    Vũ Việt Vương 01/04/2017 at 16:59

    banh

    In the beginning randomly pair the points and join the segments. Let SS be the sum of the lengths of the segments. (Note that since there are finitely many ways of connecting 2n2n points by nn segments, there are finitely many possible values of SS.) If two segments ABABand CDCDintersect at OO, then replace pairs ABABand CDCDby ACACand BDBD. Since

    AB+CD=AO+OB+CO+OD>AC+BDAB+CD=AO+OB+CO+OD>AC+BD

    by the triangle inequality, whenever there is an intersection, doing this replacement will always decrease SS. Since there are only finitely many possible values of SS, so eventually there will not be any intersection.leuleueoeobucquagianroiundefined