Отправлено: 14.05.17 19:50. Заголовок: Нестандартный в-т Богданова № 18. Не сходится ответ

Здравствуйте. После упрощения исходного выражения имею: не Da + не D6300 + D5940=1. На числовой оси "закрыты" все числа, кроме 1*6300, 2*6300 и т.д. до 32*6300. Число 33*6300=207900 кратно 3600 и кратно 5940. Вывод: минимальное А=33, этим мы перекроем все оставшиеся числа. Мой ответ не сходится с ответом = 297. Помогите, пожалуйста, разобраться. Спасибо.

 Отправлено: 14.05.17 22:42. Заголовок: Антонина, добрый веч..

Антонина, добрый вечер!
Посмотрите решение задачи 11 здесь: http://kpolyakov.spb.ru/download/inf-2015-10.pdf

 Отправлено: 16.05.17 10:37. Заголовок: Спасибо. Это, конечн..

Спасибо. Это, конечно, не строгое математическое доказательство. Я поняла так: надо найти минимальное а такое, чтобы выражение (а*6300) mod 5940 =0, чтобы обеспечить истинность исходного выражения.

 Отправлено: 16.05.17 14:57. Заголовок: Антонина, в прошлом ..

Антонина, в прошлом году я производил строгое математическое доказательство для решения заданий такого типа, даже получил явную процедуру решения, сразу приводящую к правильному ответу. К сожалению, явной формулы в терминах известных функций (min, max, НОД, НОК) получить не удалось. Мне помогали еще два человека (оба уже студенты ВМК МГУ), так что вероятность, что мы втроём пропустили что-то очень простое, очень мала.
Если Вы сдаёте ЕГЭ в этом году, то лучше не берите в голову подобные "подвохи". Шансы, что попадётся именно ДЕЛ, именно Вам и именно такого типа, ничтожно малы. Целью данного примера было продемонстрировать несовершенство некоторых имеющихся методов: за их видимой простотой стоит отсутствие универсальности. Кстати, тоже самое касается заданий с конъюнкциями.
Лично я считаю универсальным, но при этом в меру сложным, метод, предложенный Константином Юрьевичем, то есть с использованием множеств. Он применим ко всем видам задач (конечные дискретные множества, отрезки, конъюнкции, ДЕЛы), при этом методических ошибок (т.е. ошибок, когда метод срабатывает неверно при корректных входных данных) мною замечено не было. Но еще раз подчеркиваю - переучиваться сейчас слишком поздно, если привыкли решать другими методами, которые не всегда работают верно. Единственно, что могу посоветовать для конъюнкций - это использовать готовую таблицу решений, которая дана в конце этой статьи: http://kpolyakov.spb.ru/download/bitwise.pdf.

 Отправлено: 16.05.17 15:05. Заголовок: Dm пишет: Единствен..

Dm пишет:

цитата:

Единственно, что могу посоветовать для конъюнкций - это использовать готовую таблицу решений, которая дана в конце этой статьи: http://kpolyakov.spb.ru/download/bitwise.pdf.

Для конъюнкций самое то - это метод, изложенный в другой статье.

 Отправлено: 16.05.17 15:11. Заголовок: Поляков, согласен. Н..

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

 Отправлено: 17.05.17 14:38. Заголовок: Спасибо за дискуссию..

Спасибо за дискуссию и ссылки. Но, вернёмся к исходной задаче. При а=33 получаем в точке 33*6300 выражение не А +не D6300 + D5940 =1. Объясните, пожалуйста, почему ответ 297, а не 33? С остальными задачами всё понятно.

 Отправлено: 18.05.17 14:25. Заголовок: Антонина пишет: выр..

Антонина пишет:

цитата:

выражение не А +не D6300 + D5940 =1

Преобразуем это выражение к виду:
(A * D₆₃₀₀) -> D₅₉₄₀ =1.

Когда оно даёт результат 1? Всегда, кроме случая A * D₆₃₀₀ = 1 и D₅₉₄₀ = 0.
Как этого избежать? "Подогнать" первую скобку таким образом, чтобы она становилась равна 1 только в том случае, когда и D₅₉₄₀ = 1!

Далее. Что значит, что D₅₉₄₀ = 1? Это значит, что среди делителей x есть некоторая комбинация всех делителей 5940: 5940 = 2²*3³*5¹*7⁰*11¹. Обратите внимание, здесь я выписал все простые делители с учетом их кратности.


А что у нас есть в первой скобке? 6300 = 2²*3²*5²*7¹*11⁰ и A, которое как раз ищем. Таким образом, случай D₆₃₀₀ = 1 нам гарантирует, что x делится на 2², 3², 5², 7¹, 11⁰ и их всевозможные комбинации. Нам же нужно, чтобы x обязательно делился на 2², 3³, 5¹, 7⁰, 11¹.

Очевидно, что 11¹ должно быть добавлено в A. Но почему также надо добавить не 3¹ (как предлагаете Вы), а именно 3³? Потому что 2²*3²*5²*7¹*11⁰ гарантирует делимость на 9, но не на 27! И если в A добавить 3¹, то это гарантирует делимость A только на 3. В итоге мы обеспечили делимость на 9 и на 3, но не на 27!

Теперь приведу пример явного x, при котором для ответа A = 33 возникнет ошибка. Например, НОК(6300; 33) = 69300 по определению делится и на 6300, и на 33. Но попробуйте сами, что будет при делении на 5940.

 Отправлено: 19.05.17 12:39. Заголовок: Благодарю! Мне не хв..

Благодарю! Мне не хватало для понимания явного значения х=69300!
Спасибо за терпение и уделённое время.

 Отправлено: 19.05.17 12:50. Заголовок: Антонина, пожалуйста..

Антонина, пожалуйста. Как раз меня уже спрашивали на счёт этого номера, так что теперь будет, куда их перенаправить. :-)