2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 41, 42, 43, 44, 45, 46, 47 ... 56  След.
 
 Re: Обсуждение и разбор марафонских задач
Сообщение23.09.2018, 21:43 
Заслуженный участник
Аватара пользователя


09/09/14
6324
Ariadna H в сообщении #1340890 писал(а):
Анимация к задаче ММ233
Спасибо, понравилось!

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение30.09.2018, 10:25 
Заслуженный участник


27/06/08
3556
Волгоград
По одной многочисленной просьбе разбор решения ММ234 отложен на сутки.
Соответственно, решения, присланные в эти сутки будут рассмотрены и, возможно, засчитаны.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение01.10.2018, 09:03 
Заслуженный участник


27/06/08
3556
Волгоград
===========ММ234===============

ММ234 (5 баллов)

Функция $g(n)$ натурального аргумента $n$ задается так:
Пусть $n$ натуральное число. Определим $f(n)$ как число, полученное удалением последней цифры из десятичной записи $n$, увеличенное на квадрат этой цифры.
Например, $f(576) = 57 + 36 = 93$.
Тогда $g(n)  = |\{n, f(n), f(f(n)), f(f(f(n))), \dots \}|$.
Пусть $a$ и $b$ – 2018-значные числа. Может ли оказаться, что $g(a) = g(b) + 26$?

Решение

Привожу решения Юрия Варламова (минималистическое) Василия Дзюбенко (более развернутое) и vpb (солидное).

(Решение vpb)

Решение задачи ММ234

Обозначим $f^{(k)}(n)=f(f(f...(n)))$ ( $f$ применяется $k$ раз), $f^{(0)}(n)=n$.
Общая идея такова: при большом $n$ $f(n)\approx n/10$. Последовательность $x_k=f^{(k)}(n)$ ведет себя примерно как $n/10^k$, а ближе к концу начинает колебаться, и в конце зацикливается.

Разобьем решение на несколько мелких утверждений.
1) Лемма. Пусть $a$, $b$ --- постоянные, $a\ne1$, и последовательность $(y_n)$ удовлетворяет условию $y_n=ay_{n-1}+b$, $\forall\ n$. Тогда всегда
$$ y_{n+k}=a^ky_n+\frac{a^k-1}{a-1}b\,.$$

Доказательство --- очевидной индукцией по $k$.

2) Всегда $f(n)\leq(n+801)/10$ и $f(n)\geq n/10$.
Действительно, пусть $r$ --- последняя цифра в $n$, тогда
$f(n)=(n-r)/10+r^2=n/10+(r^2-r/10)\leq n/10+(9^2-9/10)=n/10+801/10$.

3) Если $n\leq89$, то $f(n)\leq89$.
Очевидно следует из 2).

4) Если $n>89$, то $f(n)<n$.
Действительно, если $n>89$, то $(n+801)/10<n$, и тем более $f(n)<n$.

Из 3), 4) следует, что $X=\{1,2,\ldots,89\}$ --- инвариантное множество и
аттрактор для $f$. Непосредственно выясняя, как действует $f$ на $X$, можно
найти значения $g$ на $X$; в частности, $g(n)$ принимает на $X$ все значения
между $1$ и $26$; $g(1)=g(89)=1$, $g(48)=26$ .
Также, циклы для $f$, т.е. такие подмножества $\{x_1,\ldots,x_t\}$,
которые $f$ переставляет по циклу, суть $\{1\}$, $\{89\}$, и $\{9,81\}$.

5) Если $n$ --- 2018-значно, то $g(n)\geq2017$. Значение $g(n)=2017$
достигается.

Действительно, $n$ последовательно уменьшается под действием $f$, пока не
попадает в $X$. При этом, как следует из второго утверждения в 2), число
цифр в $n$ всегда уменьшается не более чем на 1. Любое число в $X$ одно-
или двузначно. Поэтому, чтоб добраться от $n$ до него, надо сделать по
крайней мере 2016 шагов, откуда $g(n)\geq2017$.
При $n=89\cdot10^{2016}$ эта оценка достигается.

Дальше хотим оценить $g(n)$ сверху.

6) Всегда $f^{(k)}(n)\leq 10^{-k}n+89$.
Индукция по $k$, с использованием 2). База $k=0$ очевидна. Шаг:
$$f^{(k+1)}(n)=f(f^{(k)}(n))\leq \frac{f^{(k)}(n)}{10}+\frac{801}{10} \leq \frac{10^{-k}n+89}{10}+\frac{801}{10}=10^{-(k+1)}n+89.$$

7) Используя 4) и таблицу значений $g(n)$ при $n\leq89$, легко найти значения
$g(n)$ при $90\leq n\leq 192$. В частности, максимальное значение есть $g(126)=27$.

8) Заметим следующее: если $n'=f^{(k)}(n)$ не лежит в каком-либо цикле, то
$g(n)=k+g(n')$. (Это ясно).

9) Если $n\leq 10^{2018}-1$, то $g(n)\leq2043$.
Действительно, рассмотрим $n'=f^{(2016)}(n)$. Тогда
$$n'\leq 10^{-2016}(10^{2018}-1)+89\leq100-10^{-2016}+89,$$
откуда на самом деле $n'\leq188$. По 7), $g(n')\leq27$. Значит $g(n)=2016+g(n')\leq 2043$.

10) Теперь покажем, что верхняя оценка для $g(n)$ достигается. Для $n\geq90$ определим
$$ h(n)=10(n-81)+9=10n-801. $$
Тогда довольно ясно, что $h(n)>n$ и $f(h(n))=n$, откуда $g(h(n))=g(n)+1$. Мы возьмем $N=h^{(2016)}(126)$. Легко посчитать, используя 1), что $N=37\cdot10^{2016}+89$ --- 2018-значное. $g(N)=2016+g(126)=2016+27=2043$.

Таким образом, искомые $a$ и $b$ существуют. Чем задача и решена.


Обсуждение

Большая разрядность чисел в условии, кроме очевидной отсылки к году проведения конкурса, призвана устранить прямое переборное решение.
Но, разумеется, это лишь некая "дымовая завеса". Разность 26 достигается уже для трехзанчных чисел и больше не меняется с ростом разрядности. Я полагаю, что это заметили все конкурсанты. Но, в условиях дефицита красивых обобщений, я поощрил дополнительным тех, кто явно сформулировал этот момент.
Еще один дополнительный балл, получил vpb (за лемму 1, без которой в решении вполне можно обойтись). И это тоже свидетельство некоторой тоски ведущего о реально серьезных обобщениях и интересных аналогах конкурсных задач.
Я был почти уверен, что многие конкурсанты рассмотрят наиболее напрашивающиеся аналоги ММ234 для других систем счислеия, других степеней последней цифры. И, возможно, иные.
Однако, к другим системам счисления обратился лишь Владимир Дорофеев. Он заметил, что аналог петли 89 имеется для всех оснований ситемы счисления, больших 2, и наличие петель для систем с основанием $k^2-k+1$. Например, в семеричной системе $g_7(13)=g_7(24)=1$. Однако и Владимир не пошел дальше рассмотрения одноэлементных циклов.
Честно признаюсь, и сам ведущий поленился рассматривать естественные обобщения данной задачи. В отличие от ряда других.

Награды

За решение задачи ММ233 участники Марафона получают следующие призовые баллы:

Владимир Дорофеев - 6;
Василий Дзюбенко - 6;
Анатолий Казмерчук - 6;
vpb - 6;
Юрий Варламов - 5;
Валентина Колыбасова - 5;
Виктор Филимоненков - 5;
Евгений Гужавин - 5;
Владимир Чубанов - 5;
Владислав Франк - 5.

Эстетическая оценка задачи - 4.6 балла


Вложения:
Комментарий к файлу: Решение Юрия Варламова
234-Варламов.pdf [208.62 Кб]
Скачиваний: 121
Комментарий к файлу: Решение Василия Дзюбенко
Dziudenko_MM234.pdf [131.55 Кб]
Скачиваний: 121
 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение07.10.2018, 10:22 
Заслуженный участник


27/06/08
3556
Волгоград
===========ММ235===============

ММ235 (7 баллов)

Существует ли выпуклый многогранник, у которого равны: количество ребер; количество диагоналей; суммарное количество диагоналей граней?

Решение

Привожу решения Виктора Филимоненкова и Анатолия Казмерчука.

Обсуждение

Некоторые участники конкурса посчитали стартовую цены ММ235 завышенной. Но тот факт, что сразу несколько конкурсантов, приславших решение предыдущих задач, не отозвались на ММ235, свидетельствует, что задачка не так уж и проста.

В качестве верного ответа засчитывалось предъявление требуемого многогранника в любой форме: изображение в параллельной проекции, граф, словесное конструирования путем разрезания и наращивания известных тел, модель (правда, моделей никто не прислал :-))

Один дополнительный балл начислялся либо перечисление всех (с точностью до вектора граней) подходящих многогранников, либо за доказательства конечности их числа. Естественно наличие обоих данных условий давало два балла.

Награды

За решение задачи ММ235 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 9;
Виктор Филимоненков - 9;
vpb - 8;
Константин Шамсутдинов - 8;
Валентина Колыбасова - 8;
Владимир Чубанов - 8;
Владислав Франк - 7.

Эстетическая оценка задачи - 4.7 балла


Вложения:
Комментарий к файлу: Решение Виктора Филимоненкова
fiviol_ММ235.docx [29.06 Кб]
Скачиваний: 113
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_mm_235.docx [225.35 Кб]
Скачиваний: 141
 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение10.10.2018, 00:56 
Заслуженный участник
Аватара пользователя


09/09/14
6324
VAL
В задаче 236 речь идёт об абсолютном минимуме для всех $n$ или своём минимуме для каждого $n$ (то есть о формуле зависимости минимума от $n$)?

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение10.10.2018, 06:57 
Заслуженный участник


27/06/08
3556
Волгоград
grizzly в сообщении #1344989 писал(а):
VAL
В задаче 236 речь идёт об абсолютном минимуме для всех $n$ или своём минимуме для каждого $n$ (то есть о формуле зависимости минимума от $n$)?
Об абсолютном для всех $n$.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 10:15 
Заслуженный участник


27/06/08
3556
Волгоград
===========ММ236===============

ММ236 (7 баллов)

Натуральные числа от 1 до $4n$ разбили на четыре группы по $n$ чисел в каждой. Оказалось, что произведение всех чисел из первой группы равно произведениям всех чисел из второй и третьей групп. Найти наименьшую возможную сумму чисел четвертой группы.Существует ли выпуклый многогранник, у которого равны: количество ребер; количество диагоналей; суммарное количество диагоналей граней?

Решение

Привожу решения Виктора Филимоненкова (мне понравилось его доказательство минимальности ответа), Юрия Варламова (с принципиально иным подходом к доказательству минимальности) и Анатолия Казмерчука (с хорошей оценкой на подходящие $n$ для обобщения задачи).

Обсуждение

Наиболее сложной частью решения данной задачи оказалось внимательное прочтение условия. Сразу три конкурсанта решали другую задачу, в которой произведение чисел первой группы равнялось не произедениЯМ чисел из второй и третьей групп, а произведениЮ этих произведений. Причем один из них не "исправился" даже после явного указания на этот момент.

Основным недочетом решения было недостаточно строгое обоснование минимальности найденного ответа. Лично меня вполне убеждает реплика типа "ясно, что с дальнейшим ростом $n$ сумма чисел в 4-й группе будет возрастать". Но балл я, все таки, снимал. Тем более, что я не вовсе не уверен в монотонности этого роста.

Другие неточности были связаны с тем, что один из конкурсантов "прозевал" требуемое разбиение для $n=10$ и нашел его только для $n=11$, а другой наоборот не заметил разбиения для $n=11$. Последнее, правда, вовсе и не требовалось (при наличии разбиения для $n=10$), но это не повод, чтобы утверждать, что его нет :-)

Задача просто напрашивается на обобщения. Выражу эти обобщения в виде двух предположений:

1. Для любого натурального $k$ найдется натуральное $n$ такое, что числа от 1 до $kn$, можно разбить на $k$ групп по $n$ чисел так, что произведения чисел во всех группах, за исключением одной, будут одинаковы.
2. Для любого натурального $k$ найдется натуральное $n_0$ такое, что для любого натурального $n\ge n_0$ числа от 1 до $kn$, можно разбить на $k$ групп по $n$ чисел так, что произведения чисел во всех группах, за исключением одной, будут одинаковы.

Тех конкурсантов, которые высказали подобные гипотезы, я поощрял дополнительным призовым баллом. Еще одним баллом поощрялись оценки снизу для подходящих $n$ для разных количеств групп. Разглядеть следы этих поощрений в разделе "Награды" можно не всегда, поскольку они в значительной мере скомпенсировались штрафами за отмеченные выше недостатки.

Подтвердить первое утверждение мне удалось пока лишь для $k=5$. Подходящее $n$ оказалось равно 440. Оно хорошо согласуется с оценкой из решения Анатолия и, по-видимому, является минимальным.
В особую группу в этом случае можно включить числа:
47, 59, 71, 73, 79, 83, 97, 101, 103, 113, 127, 139, 149, 151, 157, 158, 163, 167, 191, 193, 194, 197, 199, 211, 223, 226, 227, 229, 233, 239, 241, 277, 278, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 382, 383, 386, 389, 394, 397, 398, 401, 409, 417, 419, 421, 422, 431, 433, 439, 554, 557, 562, 563, 566, 569, 571, 573, 577, 586, 587, 593, 599, 601, 607, 613, 614, 617, 619, 622, 625, 626, 631, 634, 641, 643, 647, 653, 659, 661, 662, 673, 674, 677, 683, 691, 694, 698, 701, 709, 719, 727, 729, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 831, 839, 843, 849, 853, 857, 859, 863, 877, 879, 881, 883, 887, 907, 911, 919, 921, 929, 933, 937, 939, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1059, 1061, 1063, 1069, 1077, 1087, 1091, 1093, 1097, 1103, 1109, 1114, 1117, 1123, 1126, 1129, 1138, 1142, 1151, 1153, 1154, 1163, 1171, 1174, 1181, 1186, 1187, 1193, 1198, 1201, 1202, 1213, 1214, 1217, 1223, 1226, 1229, 1231, 1234, 1237, 1238, 1249, 1259, 1262, 1277, 1279, 1282, 1283, 1286, 1289, 1291, 1294, 1297, 1301, 1303, 1306, 1307, 1318, 1319, 1321, 1322, 1327, 1346, 1354, 1361, 1366, 1367, 1373, 1381, 1382, 1399, 1402, 1409, 1418, 1423, 1427, 1429, 1433, 1438, 1439, 1447, 1451, 1453, 1454, 1459, 1466, 1471, 1478, 1481, 1483, 1486, 1487, 1489, 1493, 1499, 1502, 1511, 1514, 1522, 1523, 1531, 1538, 1543, 1546, 1549, 1553, 1559, 1567, 1571, 1574, 1579, 1583, 1594, 1597, 1601, 1607, 1609, 1613, 1618, 1619, 1621, 1622, 1627, 1637, 1642, 1646, 1654, 1657, 1658, 1663, 1667, 1669, 1671, 1678, 1679, 1689, 1693, 1697, 1699, 1706, 1707, 1709, 1713, 1714, 1718, 1721, 1723, 1726, 1731, 1733, 1741, 1747, 1753, 1754, 1759, 1761, 1762, 1766, 1774, 1777, 1779, 1783, 1787, 1789, 1797, 1801, 1803, 1811, 1814, 1817, 1821, 1822, 1823, 1831, 1838, 1839, 1847, 1851, 1857, 1858, 1861, 1867, 1871, 1873, 1874, 1877, 1879, 1882, 1889, 1893, 1894, 1901, 1906, 1907, 1909, 1913, 1923, 1927, 1929, 1931, 1933, 1934, 1937, 1941, 1942, 1949, 1951, 1954, 1959, 1963, 1966, 1973, 1977, 1979, 1982, 1983, 1987, 1993, 1994, 1997, 1999, 2003, 2011, 2017, 2018, 2019, 2026, 2027, 2029, 2031, 2038, 2039, 2041, 2042, 2049, 2053, 2059, 2062, 2063, 2066, 2069, 2073, 2078, 2081, 2083, 2087, 2089, 2098, 2099, 2102, 2103, 2111, 2113, 2122, 2123, 2126, 2127, 2129, 2131, 2137, 2138, 2141, 2143, 2147, 2153, 2157, 2161, 2167, 2173, 2174, 2179, 2181, 2182, 2186, 2189, 2194, 2199
Я, правда, поленился разбивать остальные 1760 чисел отрезка $[1..2200]$ на 4 группы по 440 чисел с произведениями
2504958280188081419921948972441396317993403801235686917189404793494410952319221107430699726426543482893150616818461328275525066728687821299944018804591123621764708436862923779082966701604255562735809
1289805092573842321119037749653748128030277852462704135079581240704766941274957290255116129389746051106781284949262988305500523148052986768314929608953462205114770269799533777220776888022882268969186
8256939455438775400312990802515143584992001317970206751063207265933958654529870772678667922698614937697266272985614883442793368986129518695143853094690122842913111643945798988875703895754483271038238
5182286564472391875215890301211571968504622359098107301057543005228410333158529079435309905796210654850747735976571461993013928271912292976427305555810117105923392750217796599906972251697366242580020
6575367017793348811892036002082886312661321854126266243791495009659816597145491149452188822078532158201083317945464571775879624578222350271609362065397049910467258829985447414830630497759605272939234
1842004607084907601089731497294700874743226451167075020005453698345376641104337205715485217753202924728864257010129270319864299599985377280000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000.
Но, учитывая, что произведение этих чисел в точности равно 4-й степени вышеприведенного числа, я уверен, что это возможно.

Что касается второй гипотезы, полагаю, что для $k=4$ подходит $n_0=28$. Среди $n$, меньших $n_0$ требуемое разбиение возможно для $n \in \{10,11,14,15,18,20,22,23,24,25,26\}$. Я не искал требуемого разбиения для большинства этих $n$, ограничившись составлением 4-й группы, для которой произведение остальных чисел является точным кубом.
Моя уверенность в том, что $n_0=28$ базируется на том, что бОльших чисел 4-я группа составляется со все возрастающим запасом (из отрезка $[1..4n]$ можно изъять существенно меньше $n$ чисел так, что произведение остальных будет кубом). Но точного доказательства у меня нет.

Награды

За решение задачи ММ236 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 9;
Виктор Филимоненков - 7;
Валентина Колыбасова - 7;
Владислав Франк - 7;
Евгений Гужавин - 7;
Владимир Дорофеев - 7;
Юрий Варламов - 7;
Дмитрий Курашкин - 6;
Владимир Чубанов - 6;
Константин Шамсутдинов -3.

Эстетическая оценка задачи - 4.6 балла


Вложения:
Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_mm_236.docx [32.9 Кб]
Скачиваний: 115
Комментарий к файлу: Решение Юрия Варламова
236-Варламов_.pdf [354.44 Кб]
Скачиваний: 118
Комментарий к файлу: Решение Виктора Филимоненкова
fiviol_ММ236.docx [15.17 Кб]
Скачиваний: 112
 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 15:08 
Заслуженный участник


06/07/11
5622
кран.набрать.грамота
VAL в сообщении #1346074 писал(а):
Лично меня вполне убеждает реплика типа "ясно, что с дальнейшим ростом $n$ сумма чисел в 4-й группе будет возрастать". Но балл я, все таки, снимал.
А почему снимали, если вас это убеждает? Для каждого следующего $n$ по сравнению с предыдущим из 4-й группы убираются меньшие числа и добавляются большие. Кстати, в качестве дополнительной задачи можно было бы поискать хоть один пример немонотонности. То есть если обозначить минимально возможную сумму чисел 4-й группы для данного $n$ как $S_n$, то найти такое $n$, для которого $S_n < S_{n-1}$.

А кто-нибудь знает алгоритм формирования 4-й группы? Не так, чтобы на глазок выбирать, а чтобы запрограммировать можно было? Можно будет попробовать продолжить поиски. Я написал программу, которая делает все вплоть до переноса в 4-ю группу "хвоста распределения" - то есть простых чисел, которые входят в $(4n)!$ со степенями 2 и меньше. А вот дальше считал вручную. Осталось чуть-чуть дописать, но идей никаких.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 15:33 
Заслуженный участник


27/06/08
3556
Волгоград
rockclimber в сообщении #1346157 писал(а):
VAL в сообщении #1346074 писал(а):
Лично меня вполне убеждает реплика типа "ясно, что с дальнейшим ростом $n$ сумма чисел в 4-й группе будет возрастать". Но балл я, все таки, снимал.
А почему снимали, если вас это убеждает?
Ну, убежденность - это одно, а доказательство - другое. Я, например, убежден, что простых близнецов бесконечно много. Но это пока не доказано. Хотя, полагаю не долго осталось жить этому утверждению в статусе гипотезы.

Возвращаюсь к ММ236. Тут все не так просто. Может оказаться, что с увеличением $n$ новых простых не добавится, но при этом пара чисел $p$ и $2p$ уйдут из 4-й группы, поскольку $3p$ станет меньше $n$. Правда, при этом могут возрасти степени меньших простых чисел и перестать быть кратными 3. В общем, не так все очевидно.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 16:07 
Заслуженный участник
Аватара пользователя


09/09/14
6324
rockclimber в сообщении #1346157 писал(а):
все вплоть до переноса в 4-ю группу "хвоста распределения" - то есть простых чисел, которые входят в $(4n)!$ со степенями 2 и меньше.
Предлагаю так:

1. Вы уже выбрали первую часть группы 4.
2. После этого выбираем числа, которые больше $\sqrt{4n}$ и степени которых не кратны 3.
3. Часть этих чисел попадут в группу 4 (ровно столько, чтобы обократнить трём показатели оставшихся).
4. Если излишков показателей по модулю 3 у чисел из п.2 в сумме с мощностью части п.1 получилось больше $n$, конец алгоритма;
4.1 Иначе -- нужно смотреть, можно ли удалить часть выбранных в п.2 чисел так, чтобы все младшие множители остались при кратных 3 степенях (никто не сомневается, что при $n>1$ это получится сделать -- здесь понадобится простой "set covering", который при не очень больших $n$ можно будет тупо перебрать);
5. Если после этого нужно будет добавить ещё чисел в группу 4 -- добрасываем кубами мелких чисел или делаем ещё один set covering.

Думаю, что если решение существует, то так его всегда можно будет найти. Но для пущей сложности и надёжности можно ещё пытаться последние 2 пункта объединить в одно целое.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 18:39 
Заслуженный участник


27/06/08
3556
Волгоград
grizzly в сообщении #1346193 писал(а):
Предлагаю так:[..]
Вы полагаете, я приведенную в обсуждении из 440 чисел руками искал?! :wink:

Приблизительно по описанной Вами схеме. Правда, не самостоятельной программкой, а неким гибридом в maple.
Подробности сейчас не помню. Дело было еще в апреле.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 19:33 
Заслуженный участник
Аватара пользователя


09/09/14
6324
VAL в сообщении #1346240 писал(а):
Вы полагаете, я приведенную в обсуждении из 440 чисел руками искал?! :wink:
Нет, конечно, я всего лишь полагаю, что если уважаемый rockclimber заинтересуется, то у нас может появиться статистика разбиений до $10^{10}$ групп :D

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 20:27 
Заслуженный участник


06/07/11
5622
кран.набрать.грамота
Я не то чтобы сильно заинтересовался, просто основная часть программы уже написана. Если чуть доработать, то можно ее просто запустить, и пусть молотит числа до посинения.
grizzly в сообщении #1346193 писал(а):
4.1 Иначе -- нужно смотреть, можно ли удалить часть выбранных в п.2 чисел так, чтобы все младшие множители остались при кратных 3
Так тут вся соль в том, как именно "нужно смотреть". Я же не могу сказать компьютеру "ну ты посмотри там".
Пока алгоритм вырисовывается такой:
1. Числа, которые входят в $(4n)!$ со степенями 1 или 2 - убираем все.
2, Числа, которые больше $\sqrt{4n}$, но которые входят со степенями, не кратными 3, нужно убрать 1 или 2 таких числа. Если нужно убрать одно - то само это число, а если два - тут возможны варианты. И проблема еще в том, что нужно учитывать, сколько именно нужно убрать чисел. Вот тут я не уверен, но думаю, может, начать программировать, а потом посмотреть, чего не хватает.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 21:04 
Заслуженный участник
Аватара пользователя


09/09/14
6324
rockclimber в сообщении #1346277 писал(а):
Если нужно убрать одно - то само это число
Нет, тут тоже те же варианты.
Я думаю, что если Вы пройдёте руками этот алгоритм для $n=11$ (это займёт от силы пару минут), тогда всё станет просто и понятно. Там после шага 1 (который Ваш) останется убрать только одно число, кратное 11. Там этих чисел 4, но убрать нужно именно число 33 -- тогда все остальные степени станут кратными трём.

 Профиль  
                  
 
 Re: Обсуждение и разбор марафонских задач
Сообщение14.10.2018, 22:30 
Заслуженный участник


06/07/11
5622
кран.набрать.грамота
grizzly в сообщении #1346290 писал(а):
Я думаю, что если Вы пройдёте руками этот алгоритм для $n=11$
Руками я его проходил уже, спасибо, что напомнили (я - тот самый участник, который нашел решение для $n=11$, но проскочил $n=10$ :oops: ).
Тогда наверное так (шаги те же, что и в предыдущем сообщении)
1) Все то же самое, но дополнительно запоминаем, что с каждым простым числом, которое входит в факториал 2 раза, мы дополнительно убираем одну двойку
2) Для чисел больше $\sqrt{4n}$ считаем, сколько их надо убрать (эти числа хороши тем, что их квадраты в факториал не входят, поэтому их посчитать проще). Соответственно, каждому такому числу может соответствовать некоторая степень одного из маленьких чисел (меньше $\sqrt{4n}$). Тут нужно посчитать, сколько мест осталось в 4-й группе. На примере $n=11$ - решить, убирать $3$ и $11$ или $33$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 838 ]  На страницу Пред.  1 ... 41, 42, 43, 44, 45, 46, 47 ... 56  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group