Vrijeme: 22:24

Ekvilibrići #4

Promotrimo graf G s vrhovima \{0, 1, 2, 3, 4, 5, 6, \ldots, 10000 \} i bridovima \{ \{0,1\}, \{0,2\}, \{0,3\}, \{0, 4\}, \{0,5\} \}, te \{k, k+5\} za k \in \{1, 2, \ldots, 9995 \}. Svaki od vrhova obojan je u crno ili u bijelo. Za bojanje kažemo da je ekvilibrij od G ako ne postoji vrh kojem možemo promijeniti boju, a da povećamo broj bridova koji spajaju raznobojne vrhove. Koliko različitih ekvilibrija od G postoji? (Napišite samo zadnjih 6 znamenaka odgovora.)