Прозаседавшиеся (арифметическая задача)

[VAL]

В.Пупкин, ассистент одной из математических кафедp N-ского унивеpситета,
скучал на заседании кафедpы. Взгляд его блуждал, останавливаясь то на затылках
сидящих впеpеди доцентов, то на лице заведующего, то на поpтpете одного из
светил отечественной математической науки, висевшем над головой завкафедpой,
левее таблицы фактоpиалов натуpальных чисел, не пpевосходящих 50. Под поpтpетом
были указаны имя и годы жизни ученого. От нечего делать Пупкин пеpемножил год
pождения светила на год pождения завкафедpой. Поскольку доклад последнего о
меpопpиятиях по повышению качества учебного пpоцесса в пpедстоящемм учебном году
все не кончался, Пупкин домножил полученное пpоизведение на год своего pождения,
а затем на годы pождения маячивших впеpеди доцентов.
"Сосчитав" последнего доцента Пупкин с удивлением обнаpужил, что pезультат его
усеpдных вычислений совпал с одним из чисел в таблице фактоpиалов.

Сколько доцентов сидело между Пупкиным и завкафедpой?
Поpтpет какого математика он лицезpел на заседании кафедpы?

[maxal]

Владимир, приветствую на нашем форуме!
Для несведущих: Владимир - это автор и постоянный ведущий Математического Марафона. Надеюсь, скоро он нас порадует новыми нестандартными задачками.

А представленная задача представляет хороший шанс продемонстрировать возможности PARI/GP - в качестве приложения к моему введению в PARI/GP - чем я не премину воспользоваться.

Прежде чем решать задачу, нужно сделать некоторые предположения. Я буду считать, что г.р. (год рождения) присутствующих доцентов и самого Васи (для простоты изложения в дальнейшем будем причислять Васю к доцентам и считать, что он самый молодой из них) лежат в отрезке $[1900,2008]$ - с запасом: мне $108$-летние и новорождённые доценты незнакомы :) А математик на портрете, будем считать, родился в отрезке годов $[1000,1899]$. Если я ошибся в своих предположениях, то решение отыскать не удастся, и скоро мы узнаем это. Или же, если эти рамки слишком широкие, решений будет много, но бестолковых :)

Для начала отберём те года из отрезка $[1900,2008]$, что не содержат простых делителей $>50$, - понятно, что только такие могут быть г.р. доцентов:

? g=[]; for(k=1900,2008,if(vecmax(factor(k)[,1])<=50,g=concat(g,[k])))
? g
%1 = [1900, 1904, 1911, 1914, 1920, 1922, 1924, 1925, 1927, 1932, 1935, 1936, 1938, 1944, 1950, 1953, 1955, 1960, 1968, 1972, 1974, 1976, 1978, 1980, 1984, 1989, 1995, 1998, 2000, 2001, 2002]
? n=#g
%2 = 31

Как видим, "хороших" годов оказалось всего лишь 31.
Далее запишем их в виде столбцов матрицы $M$ размером $(m+1)\times(n+2)$, где $m=\pi(50)=15$ и $M_{ij}$ равно степени $i$-го простого в разложении $j$-го "хорошего" года ($i=1,\dots,m$ и $j=1,\dots,n$). Два дополнительных ($n+1$-й и $n+2$-й) столбца матрицы $M$ зарезервированы для г.р. математика на портрете и для факториала, который Вася нашёл в таблице (их мы будем искать перебором), а дополнительная строка нужна для трюка, который будет описан ниже.

? m=primepi(50)
%3 = 15
? M=matrix(m+1,n+2,i,j,if(i<=m&&j<=n,valuation(g[j],prime(i))))
%5 = 
[2 4 0 1 7 1 2 0 0 2 0 4 1 3 1 0 0 3 4 2 1 3 1 2 6 0 0 1 4 0 1 0 0]
[0 0 1 1 1 0 0 0 0 1 2 0 1 5 1 2 0 0 1 0 1 0 0 2 0 2 1 3 0 1 0 0 0]
[2 0 0 0 1 0 0 2 0 0 1 0 0 0 2 0 1 1 0 0 0 0 0 1 0 0 1 0 3 0 0 0 0]
[0 1 2 0 0 0 0 1 0 1 0 0 0 0 0 1 0 2 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 1 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Теперь начинаем перебор по годам рождения математика на портрете и результирующему факториалу, заполняя последние два столба нашей матрицы. Для каждой заполненной таким образом матрицы найдем $\mathbb{Z}$-базис её решётки с помощью функции matkerint, а в нем будем искать такие вектора, что $n+1$-я компонента равна $1$, и $n+2$-я компонента равны $-1$, а все остальные равны $0$ или $1$ (с точностью до знака целой строки). Мы используем дополнительную строку, чтобы гарантировать противоположные знаки у $n+1$-й и $n+2$-й компонент: а именно положим $M_{m+1,n+1}=M_{m+1,n+2}=1$.

Понятно, что решение может быть только в случае, когда в нашем базисе присутствует вектор, у которого $n+1$-я и $n+2$-я компоненты по модулю равны $1$. Но мы будем даже наглее - будем надеяться, что решение возникнет непосредственно как элемент базиса. Дальнейшее показывает, что наша наглость обоснована - таких решений довольно много:

? M[m+1,n+1]=M[m+1,n+2]=1
%6 = 1
? for(h=1000,1899, if(vecmax(factor(h)[,1])>50,next); for(i=1,m,M[i,n+1]=valuation(h,prime(i))); for(r=1,50, for(i=1,m,M[i,n+2]=valuation(r!,prime(i))); K=matkerint(M); sol=0; for(j=1,matsize(K)[2], if(abs(K[n+2,j])!=1,next); t=K[,j]; if(t[n+2]==1,t=-t); t[n+2]=0; if(vecmin(t)>=0 && vecmax(t)<=1, print1([h,r]); for(k=1,n, if(t[k],print1(" ",g[k])));print();  )) ))
[1344, 28] 1920 1932 1944 1980 1989 1995 2000 2002
[1368, 28] 1920 1932 1944 1960 1980 1989 2000 2002
[1386, 28] 1920 1932 1944 1960 1976 1980 1989 2000
[1404, 28] 1920 1932 1938 1944 1960 1980 2000 2002
[1408, 28] 1911 1920 1932 1944 1980 1989 1995 2000
[1440, 28] 1900 1920 1932 1944 1960 1980 1989 2002
[1458, 28] 1904 1932 1936 1944 1950 1960 1976 2000
[1485, 28] 1904 1920 1932 1944 1950 1960 1976 1980
[1512, 28] 1904 1920 1925 1932 1944 1950 1976 1980
[1536, 28] 1900 1911 1920 1925 1932 1944 1980 1989
[1539, 28] 1904 1911 1920 1932 1936 1944 1950 2000
[1584, 28] 1900 1904 1911 1920 1932 1944 1950 1980
[1600, 13] 1944 2002
[1620, 13] 1920 2002
[1620, 28] 1900 1904 1911 1920 1932 1936 1944 1950
[1638, 13] 1920 1980
[1664, 13] 1925 1944
[1728, 21] 1938 1944 1960 2000 2002
[1760, 21] 1920 1944 1960 1989 1995
[1764, 21] 1904 1944 1976 1980 2000
[1768, 21] 1920 1944 1960 1980 1995
[1782, 21] 1904 1944 1960 1976 2000
[1785, 21] 1920 1944 1960 1976 1980
[1792, 21] 1900 1944 1960 1980 1989
[1800, 21] 1920 1938 1944 1960 2002
[1820, 21] 1920 1938 1944 1960 1980
[1824, 21] 1904 1911 1944 1980 2000
[1836, 21] 1920 1925 1944 1960 1976
[1848, 21] 1900 1920 1944 1960 1989
[1862, 21] 1904 1920 1944 1950 1980
[1872, 21] 1920 1925 1938 1944 1960
[1881, 21] 1904 1911 1920 1944 2000
[1890, 10] 1920
[1890, 21] 1904 1920 1925 1944 1976

Как видим, решений нашлось много, но в них присутствуют либо слишком старые, либо слишком молодые доценты. Это наводит на мысль, что нам следует сделать возрастные рамки более жёсткими. Оставляю это читателям в качестве упражнения. Скажу лишь ответ:

Если зажать г.р. доцентов в отрезок $[1930,1990]$, то наша программа выдаст единственное решение:
[1792, 21] 1938 1944 1950 1960 1980
То есть:
зав.кафедрой ("старейшина") родился в 1938 году;
Вася в 1980-м;
доцентов на кафедре раз, два и обчёлся;
а с портрета смотрит Лобачевский.

[VAL]

maxal писал(а):

Для несведущих: Владимир - это автор и постоянный ведущий Математического Марафона. Надеюсь, скоро он нас порадует новыми нестандартными задачками.

Я тоже на это надеюсь.
Но новые задачи будут с сентября.
А пока постараюсь порадовать старыми.

Цитата:

А представленная задача представляет хороший шанс продемонстрировать возможности PARI/GP - в качестве приложения к моему введению в PARI/GP - чем я не премину воспользоваться.

Ничего не имею против PARI/GP, но все же попробую привести решение, позволяющеее обойтись без элементов программирования.

Цитата:

Прежде чем решать задачу, нужно сделать некоторые предположения. Я буду считать, что г.р. (год рождения) присутствующих доцентов и самого Васи (для простоты изложения в дальнейшем будем причислять Васю к доцентам и считать, что он самый молодой из них) лежат в отрезке $[1900,2008]$ - с запасом: мне $108$-летние и новорождённые доценты незнакомы

Граница 2008 выглядит явно завышенной Достаточно взять 1990.
А вот 1900, IMHO, в самый раз.
Не знаю, как сегодня, но пару лет назад уважаемый Сергей Михайлович Никольский еще продолжал преподавательскую деятельность. А он 1905 года рождения.
Но это крайние значения.
Средний же возраст сотрудников кафедры буду полагать лежащим в интервале $[1920,1985]$.

Цитата:

А математик на портрете, будем считать, родился в отрезке годов $[1000,1899]$.

Считаю разумным интервал $[1669,1950]$.
1669 - год рождения Л.Ф.Магницкого. Отечественные математики, родившиеся раньше, мне неизвестны.

Цитата:

Для начала отберём те года из отрезка $[1900,2008]$, что не содержат простых делителей $>50$, - понятно, что только такие могут быть г.р. доцентов:

? g=[]; for(k=1900,2008,if(vecmax(factor(k)[,1])<=50,g=concat(g,[k])))
? g
%1 = [1900, 1904, 1911, 1914, 1920, 1922, 1924, 1925, 1927, 1932, 1935, 1936, 1938, 1944, 1950, 1953, 1955, 1960, 1968, 1972, 1974, 1976, 1978, 1980, 1984, 1989, 1995, 1998, 2000, 2001, 2002]
? n=#g
%2 = 31

Как видим, "хороших" годов оказалось всего лишь 31.

Здесь явно имеются лишние числа. Про годы рождения близкие к 2000, я уже говорил.
Но дело не только в этом. Например, число 1922 не делит ни один из факториалов чисел не больших 50.

Но это частности. Подвергнем приведенный список более жесткой ревизии.
Для этого попробуем сначала найти все n, факториалы которых могли возникнуть при Васиных вычислениях.
Пусть k - количество доцентов, сидевших между Пупкиным и завкафедрой.
Согласно нашим предположениям, n и k должны удовлетворять неравенствам:
$ \sqrt[k+2]{n!/1669} > 1919$ и $ \sqrt[k+2]{n!/1950} < 1986} $

Такая пара (n, k) всего одна: n = 21, k = 3.
Теперь выпишем делители 21!, лежащие в интервале $[1900,1990]$:
1900, 1904, 1911, 1920, 1925, 1938, 1944, 1950, 1960, 1976, 1980, 1989.
Подходящие комбинации теперь легко собираются вручную. Для этого удобно взять канонические разложения 21! и потенциальных годов рождения, дабы, например, из чисел 1900, 1938, 1976, кратных 19, использовать не более одного.
Используя подобные соображения находим два подходящих набора:
1785, 1920, 1944, 1960, 1976, 1980 и
1792, 1938, 1944, 1950, 1960, 1980.
Однако не один из сколько-нибудь "корифеистых" отечественных математиков не появился на свет в 1785 году, а 1792 - год рождения Лобачевского.

Таким образом Пупкин лицезрел перед собой затылки трех доцентов, а на стене висел портрет Лобачевского.

Цитата:

Если зажать г.р. доцентов в отрезок $[1930,1990]$, то наша программа выдаст единственное решение:
[1792, 21] 1938 1944 1950 1960 1980
То есть:
зав.кафедрой ("старейшина") родился в 1938 году;
Вася в 1980-м;
доцентов на кафедре раз, два и обчёлся;
а с портрета смотрит Лобачевский.

Одного доцента недосчитал

[Алексей К.]

Чисто спасибо!

[sasha_vertreter]

maxal писал(а):

Владимир, приветствую на нашем форуме!
Для несведущих: Владимир - это автор и постоянный ведущий Математического Марафона
Для начала отберём те года из отрезка $[1900,2008]$, что не содержат простых делителей $>50$, - понятно, что только такие могут быть г.р. доцентов:

Поясните, пожалуйста, для очень медленных, почему не должно быть чисел с простыми делителями больше 50.

Спасибо (извините за банальный вопрос)

[VAL]

sasha_vertreter писал(а):

maxal писал(а):

Для несведущих: Владимир - это автор и постоянный ведущий Математического Марафона
Для начала отберём те года из отрезка $[1900,2008]$, что не содержат простых делителей $>50$, - понятно, что только такие могут быть г.р. доцентов:

Поясните, пожалуйста, для очень медленных, почему не должно быть чисел с простыми делителями больше 50.

Потому что простые больше 50 не могут входить в разлжение факториалов, не превышающих 50.