Олимпиада Туймаада по математике. Старшая лига. 2010 год

В стране учатся $4^{9}$ школьников, живущих в четырех городах. В конце учебного года правительство провело ЕГЭ по 9 предметам, за каждый из которых каждый ученик получил 1 балл, 2 балла, 3 балла или 4 балла. Известно, что у любых двух учеников отметки хотя бы по одному предмету отличаются. При этом оказалось, что у любых двух учеников, живущих в одном городе, совпадают отметки хотя бы по одному предмету. Докажите, что найдется такой предмет, что у любых двух детей, живущих в одном городе, совпадают отметки именно по этому предмету. ( Ф. Петров )