W grupie zna się dokładnie. Sprawdzenie.

[GluEEE]

Mam \(\displaystyle{ k}\) osobową grupę. Na początku każdy zna dokładnie 3 osoby, a potem dokładnie 4 osoby.
Dla jakiego \(\displaystyle{ k}\) jest to możliwe?

Problem chciałem rozwiązać na grafach.
Moje rozumowanie:
Na początku mamy graf regularny 3 stopnia. Zatem liczba krawędzi wynosi \(\displaystyle{ \frac{3k}{2}}\).
Zatem nasza liczba osób \(\displaystyle{ k}\) musi być parzysta. Potem mamy graf regularny 4 stopnia, więc liczba krawędzi wynosi \(\displaystyle{ \frac{4n}{2}}\).
Maksymalna liczba krawędzi dla grafu wynosi \(\displaystyle{ \frac{n(n-1)}{2}}\). Muszę więc rozwiązać nierówność: \(\displaystyle{ \frac{n(n-1)}{2} \ge 2n}\), z czego otrzymam \(\displaystyle{ n \ge 5}\)

Zatem \(\displaystyle{ k \in \left\{ 6, 8, 10, 12, ...\right\}}\)

Jest ok?

[Mruczek]

Na razie tylko ograniczyłeś w pewien sposób zbiór rozwiązań. Trzeba jeszcze pokazać, że rzeczywiście istnieje graf dla każdego z wyznaczonych przez Ciebie \(\displaystyle{ k}\). Tak się składa, że faktycznie istnieje, ale trzeba podać przykład.
To zadanie pochodzi z I etapu X Olimpiady Matematycznej Gimnazjalistów.
Tutaj jest firmowe rozwiązanie:

Możesz wymyśleć swoje przykłady grafów. Łatwo to zrobić np. dla \(\displaystyle{ k}\) podzielnego przez 8.