dambord

Opgave - USAMO 1999 vraag 1

Enkele dampionnen worden op een $n\times n$ zodat

  • ieder vakje dat geen damstuk bevat grenst (met een zijde) aan een vakje dat er wel één bevat,
  • gegeven twee willekeurige vakjes die beide een damstuk bevatten, bestaat er een pad (waarbij twee opeenvolgende vakjes van het pad aangrenzend moeten zijn) van het ene vakje naar het andere, waarbij op ieder vakje in dat pad een dampion bevat.

Bewijs dat er minimum $\frac{n^2-2}{3}$ damstukken op het bord staan.[/]