Колмогоров привез с собой из Германии, помимо прочего, стихи Гёте, который навсегда стал одним из любимых его поэтов. В письмах Колмогорова и Александрова друг другу можно прочитать подробные отчеты о походах на концерты и услышанной музыке. Когда появились виниловые пластинки, они начали их коллекционировать. По вторникам Александров устраивал в МГУ вечера классической музыки, принося пластинки и рассказывая о композиторах и музыке. После его смерти в ноябре 1982 года почти восьмидесятилетний Колмогоров, уже искалеченный болезнью Паркинсона, продолжил эту традицию.
Классическая музыка и мужская дружба, математика и спорт, поэзия и обмен идеями сложились в образ идеального человека и идеальной школы по Колмогорову. В возрасте примерно сорока лет он составил "Конкретный план того, как сделаться великим человеком, если на то хватит охоты и усердия". Согласно этому плану, Колмогоров должен был к шестидесяти годам прекратить занятия наукой и посвятить оставшуюся жизнь преподаванию в средней школе. Он действовал в соответствии с планом. В 1950-х Колмогоров испытал новый творческий подъем и публиковался почти так же активно, как тогда, когда был тридцатилетним (это очень необычно для математика), а после остановился и обратил все свое внимание на школьное образование.
Весной 1935 года Колмогоров и Александров организовали в Москве первую математическую олимпиаду для детей. Это помогло заложить фундамент международных математических олимпиад. Четверть века спустя Колмогоров объединил усилия с Исааком Кикоиным, неофициальным лидером советской ядерной физики, с подачи которого в СССР начали проводить школьные олимпиады по физике. Поскольку единственной ценностью, которую государство видело в математике и физике, было их военное применение, Колмогоров и Кикоин решили убедить советских лидеров в том, что элитарные физико-математические спецшколы обеспечат страну мозгами, необходимыми для победы в гонке вооружений.
Проект поддержал член ЦК КПСС Леонид Ильич Брежнев, который спустя пять лет станет главой государства. В августе 1963 года Совет министров СССР издал постановление об учреждении математических школ-интернатов, и в декабре они открылись в Москве, Киеве, Ленинграде и Новосибирске. Большинством их руководили ученики Колмогорова, который лично наблюдал за составлением учебных планов.
В августе Колмогоров организовал в подмосковном поселке Красновидово летнюю математическую школу. Были отобраны 46 победителей и призеров Всероссийской математической олимпиады. Колмогоров и его аспиранты вели занятия, читали лекции по математике и водили учеников в походы по окрестным лесам. Наконец, 19 юношей были отобраны для учебы в новой физико-математической школе-интернате при МГУ.
Они оказались в новом, странном мире. Колмогоров, который сорок лет вынашивал проект новой школы, разработал не только методику индивидуального обучения, основанную на дальтон-плане, но и полностью новую школьную программу. Лекции по математике, которые читал в том числе сам Колмогоров, имели целью ввести детей в мир большой науки. Принимались в расчет способности учеников: Колмогоров охотнее выбирал детей, в которых обнаруживал присутствие "божьей искры", чем тех, кто досконально знал школьный курс математики. В колмогоровской школе — возможно, единственной в СССР — преподавали вузовский курс истории древнего мира. Учебная программа включала большее количество уроков физического воспитания, чем их было в обычных школах. Наконец, Колмогоров лично просвещал учащихся, рассказывая о музыке, изобразительном искусстве и древнерусской архитектуре, и устраивал походы — пешие, лыжные или лодочные.
"В интернате <...> нас призывали интересоваться не только математикой и физикой, но и развиваться всесторонне. Походы и стихи нам нравились, — вспоминает один из учеников Колмогорова. — Музыку понимали немногие — она требует подготовки. Но требования интереса к "общественным наукам" нас смешили и раздражали. Хорошо, что сам Андрей Николаевич по этому поводу отмалчивался". Таким образом, Колмогоров не только стремился передать ученикам гуманистические ценности, как он их понимал, но и оберегал детей от марксистской идеологии, под воздействием которой они находились в средней школе и которую им будут упорно навязывать (и которую им вновь придется терпеть) в вузе.
Колмогоров стремился не только создать обойму элитарных математических школ. Он хотел обучить настоящей математике всех детей, которые могут учиться. Он подготовил проект модернизации учебной программы с тем, чтобы школьники учились не сложению и вычитанию, а математическому мышлению. Он курировал реформу, которая ввела в учебные планы изучение простых алгебраических уравнений с переменными и использование в обучении компьютеров — чем раньше, тем лучше. Кроме того, Колмогоров стремился преобразовать школьный курс геометрии, чтобы открыть дорогу неевклидовой геометрии.