Олимпиадные задачи по математике

За круглым столом сидят 13 богатырей из <i>k</i> городов, где  1 < <i>k</i> < 13.  Каждый богатырь держит в руке золотой или серебряный кубок, причём золотых кубков тоже <i>k</i>. Князь повелел каждому богатырю передать свой кубок соседу справа и повторять это до тех пор, пока какие-нибудь два богатыря из одного города оба не получат золотые кубки. Доказать, что желание князя всегда будет исполнено.