kms - fórum o príkladoch

14. príklad 1. zimnej série 2009/2010

Zadanie:
Na matfyze v Sydney majú každí dvaja študenti, ktorí sa navzájom nepoznajú, aspoň jedného spoločného známeho (poznanie sa je symetrické). Ani jeden študent pritom nepozná všetkých ostatných. Očíslujme študentov od $1$ po $n$ a nech $a_i$ označuje počet známych $i$ -teho študenta. Vieme, že platí

$\sum_{i=1}^{n}a_i^2=n^2-n.$

Nech $k \geq 3$ je najmenší počet študentov, ktorých možno usadiť okolo okrúhleho stola tak, aby každý poznal oboch svojich susedov. Nájdite všetky možné hodnoty $k$ .

Naspäť na príklady | Napíš príspevok