VMO 2007 — Kỳ thi quốc gia Câu hỏi 4

Cho một đa giác đều $2007$ đỉnh. Tìm số nguyên dương $k$ nhỏ nhất thoả mãn tính chất: Trong mỗi cách chọn $k$ đỉnh của đa giác luôn tồn tại $4$ đỉnh tạo thành một tứ giác lồi mà $3$ trong số $4$ cạnh của nó là $3$ cạnh của đa giác đã cho.