Question

将凸n边形A1A2…An的边与对角线染上红、蓝两色之一，使得没有三边均为蓝色的三角形．对k=1，2，…，n，记

将凸n边形A1A2…An的边与对角线染上红、蓝两色之一，使得没有三边均为蓝色的三角形．对k=1，2，…，n，记bk由顶点Ak出的蓝色边的条数，求证：b1+b2+…bn≤n22．

Answer 1

证明：不妨设b=max{b₁，b₂，…，b_n}，
并且由点A向A₁，A₂，…，A_b，引出b条蓝色边，则A₁，A₂，…，A_b之间无蓝色边，A₁，A₂，…，A_b以外的n-b个点，每点至多引出b条蓝色边，
因此蓝色边总数≤（n-b）b≤[

(n?b)+b

2

]2=

n2

4

，
故b₁+b₂+…b_n≤2×

n2

4

=

n2

2

．命题得证．