"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

Задачи на логику и сообразительность




О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!


Справочная



Признаки делимости
Площади фигур


Реклама






задача: Разность квадратов

Задачу прислал: Админ


Сложность: средняяВерно ли, что из 5 целых чисел всегда можно выбрать два таких, что разность квадратов их делится на 7?



Ответ





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





Ваши ответы на задачу


ответов: 24

< 1 2 >

бандит 2013-03-29 21:29:19 пишет:
1 2 3 4 5
1 2 9 16 25 квадраты
16-9=7/7
   Админ: это частный случай. Надо доказать для произвольных 5 чисел.

KoKos 2013-01-15 11:09:20 пишет:
:) Ну и уж завершим, с чего начали... Таким образом, обобщенная функция Хы(Пы,Эн) для нахождения наименьшего количества целых, среди которых хотя бы два такие, что разность их Эн-тых степеней делится на простое Пы - где Пы включает и двойку, а Эн - любое натуральное. Имеет вид: \n\n
Хы(Пы) = (Пы-1) / НОД( Пы-1, (Эн-1)МОД(Пы-1)+1 ) +2 \n\n
Где НОД - наибольший общий делитель, МОД - собственно помодуль, а +2 в конце для учтения пропущенного нуля, плюс одного "лишнего" числа, которое-то и обеспечит зануление.

KoKos 2013-01-15 10:04:52 пишет:
Вася Пупкин, так вот, возвращаясь к тому, чего мне не удалось уловить... :) Ферма и комплексные корни на окружности - это красотища, несомненно и искренне. Но есть два "но". ;))) Во-первых, очевидно, что "степени-зануляшки" у нас должны быть не делителями Пы-1, а просто иметь с Пы-1 некоторый общий делитель. Во-вторых, такое комплексное "колесо" нам поможет только именно для подсчета количества подгрупп, но не качества. Поворачиваем колесо на нужную степень и считаем оставшиеся в нем "спицы". То бишь, то самое Хы(Пы), с которого все начиналось, мы, конечно легко найдем, для данной конкретной степени. А вот для построения актуальных подрупп и/или нахожения соответствующих помодулей степеней нам надо поставить в соответствие спицам конкретные помодули (см. рисунок) - и как сделать именно это без привлечения терминаторов, я что-то не вижу пока. Видать, опять что-то пропустил? :)


KoKos 2013-01-15 03:03:25 пишет:
Не совсем уловил, сплю уже, сорри. А что с четвертой степенью? Она-то не является делителем (7-1). А тривиальное ненуление дает. :)

Вася Пупкин 2013-01-15 02:26:54 пишет:
Тьфу, дурак. Кокос, все там просто, если отбить на одно из чисел -- мы ищем, выходит, корни энтой степени из единички по модулю Пы. Малая т. Ферма -- это как раз о том, что их таких Пы. Без нуля -- Пы-1. Группа из Пы элементов подгрупп не имеет, а вот из Пы-1 -- вполне, и это и есть наши тройки(в случае семерки) или пятерки(в случае одиннадцати). А те тройки занулителей, про которые я заливал, переводятся в тройку корней из единицы(точнее, в их вещественную часть) -- на окружности(комплексной) они как раз и сидят на равных углах друг от друга. Итого, зануление по простому модулю дадут только степени, являющиеся делителями Пы минус одина, для одиннадцати, к примеру -- только пятерки(тоже будет две подгруппы по пять), разности остальных степеней занулятся только тривиальным a=b. Ура, спасибо, все, туман рассеялся. Просто малую т. Ферма надо было вспомнить, а дальше все вокруг нее. Все уже украдено до нас.

Вася Пупкин 2013-01-15 01:33:51 пишет:
Кокос, ну, это Вы, вообще-то, просто малую теорему Ферма доказали мимоходом, в своем пункте 2. Единственная оговорка -- эн, естественно, не делится на пы. Нет, меня заинтриговало не количество требуемых чисел, оно-то пес с ним, а вот это самое -- как устроены пары, зануляющие (a^n - b^n)/(a-b), вот тот самый многочлен, который сумма a^k*b^(n-k) -- по модулю Пы... Что за кластеры такие образуют эти пары? Почитаю еще и осмыслю Ваши таблички -- быть может, Вы об этом и написали, но сейчас меня тут сильно отпомехивают...

KoKos 2013-01-15 01:20:15 пишет:
Лопухнул, как всегда - шестые и нулевые степени - по три числа, а не два, естественно.

KoKos 2013-01-15 01:10:28 пишет:
Вася Пупкин, несомненно, что-то большее и красившее за этим прорисовывается, но тоже пока не знаю, с какой стороны к нему подойти... \n\n
Общая картинка, естественно, с учетом того, что не все куски мозаики у нас собраны может в итоге оказаться и ошибочной, но пока что выглядит так: \n\n
Берем некоторое простое Пы нечетное (чтоб не "портить" картинку Пы=2 :) \n
1. Для всех целых Эн, Эн^1 mod Пы = Эн mod Пы. ;))) Тут и доказывать-то нечего... 8) То бишь, для замыкания полного цикла возможных разностей первой степени, потребуется ровно Пы+1 элемент.
2. Теперь, как ни удивительно, но Эн^Пы mod Пы = Эн mod Пы. :) Это показывается уже несколько сложнее, я сделал по индукции, через разложение (Эн+1)^Пы. Таким образом мы имеем две крайние точки, в которых нам потребуется максимум значений (Пы+1). Это же объясняет, почему у Вас двойка "не влезла" в исходное решение. У нее средней точки нет. :) \n\n
Теперь отходим от общего случая и возвращаемся к нашему Пы=7. Попробуем представить недостающие куски мозаики. Итак первые и седьмые степени требуют по восемь чисел. Вторые степени требуют пять чисел, смотрим симметричные им шестые: 0->0, 1->1, 2->1, 3->1, 4->1, 5->1, 6->1. 8))) Неожиданность... Похоже, что в таком случае шестые степени соответствуют нулевым (с оговоркой на неопределенность 0^0 ). И требуют всего двух чисел в исходном наборе. \n\n
Впрочем, эта неожиданность тоже легко доказывается строго, из рассмотренного выше Эн^Пы mod Пы = Эн mod Пы и свойства целочисленных помодулей Эн mod Пы * Эм mod Пы = (Эн * Эм) mod Пы. \n\n
Давайте уже глянем на четвертые и пятые степени, для комплекта - это недолго. \n
4: 0->0, 1->1, 2->2, 3->4, 4->4, 5->2, 6->1. Опять пять чисел в наборе. \n
5: 0->0, 1->1, 2->4, 3->5, 4->2, 5->3, 6->6. Снова вверх, до максимума, восемь чисел в наборе. \n\n
Имеем странную кривозубую пилу, считая количество необходимых для зануления чисел по степеням от 1 до 7: 8, 5, 4, 5, 8, 2, 8. Мне пока это больше ни о чем не говорит, кроме того, что для остальных натуральных степеней пила будет периодичной - по тому же правилу умножения.

Вася Пупкин 2013-01-14 00:23:18 пишет:
Кокос, я тут подумал -- Вы, поохоже, меня на что-то совершенно потрясающей красоты вывели, но мне слабо, по крайней мере, пока, эту красоту обосновать, а только получается так по-дикарски смотреть, ухать и танцевать. Вот смотрите, с кубами. Разложим, значит, разность кубов. Ну, вылетевшая разность нам ничего нового не скажет, а вот посмотрим на a^2+ab+b^2. Когда такая плюшка занулится по модулю 7? Посмотрим опять на возможные остатки по модулю 7 -- они, кроме нулевого, разделяются на две тройки: (1,2,4) и (3,5,6). Чем эти тройки замечательны? А вот чем. Во-первых, сумма каждой тройки нулится(я буду опускать затрахавшее "по модулю 7"). Во-вторых, в квадратах первая тройка переходит в себя, а вторая -- в первую. Но самое главное -- любая пара из каждой тройки зануляет наш многочлен(ну, произведение в паре всегда равно оставшемуся члену тройки). Эти самые тройки(а не двойки, как было с квадратами) и определяют допустимые для ненуля значения остатков, вот отсюда и получаются максимум три числа, как Вы и сказали(по одному из каждой тройки, и одно из нуля). Если просимметрить картинку вокруг нуля, наши тройки превращаются в (-3,1,2) и (-2,-1,3), совсем красиво(семь остатков с центром в нуле и двумя симметричными зануляющимися тройками). Вот эти самые тройки -- какой-то жуткой красоты, и, наврное, что-то огромное и красивое общее за этим маячит, но что -- хз. Хочется так же раздраконить пятые степени -- может, там понятнее станет. Хотя и так видно, что такого же уюта с пятью слагаемыми вроде бы не светит. Но это, может, потому, что пять уже слишком близко к семи, и вместо семерки надо брать большее простое, типа, скажем, одиннадцати. Увы, я не люблю и не умею экселить, и на бумажки аллергия... Но грю же -- явно какой-то уголок какого-то офигезно красивого замка просматриватся, какая-то теоретико-числовая магия, но мне не хватает ни образования, ни одаренности, ни правильного пятого пункта. Говорят, великий теорчисловик -- это беспременно русский и на голову поеханный: Виноградов там, Шафаревич... А зато они бы, может, сразу сказали бы тривиальный общий результат...

KoKos 2013-01-12 03:57:54 пишет:
Вася Пупкин, с изначальным решением у Вас все в порядке (вроде бы, все еще не проверял, если честно). \n\n
А что касается куртуазных бесед, - то уж покорнейше прошу прощения. Мы с Вами - разные люди и, вполне естественно, имеем разные подходы к решению одних и тех же задач. А так, да, Ваш стиль меня порой коробит - но содержание беседы доставляет много больше удовольствия. :)))

Вася Пупкин 2013-01-12 02:32:02 пишет:
Да, похоже, с обобщением это я таки сгвоздил -- Кокос, спасибо, Админ, игнорьте мое "упрощение" -- а то, может, даже и "решение": это, похоже, случайное совпадение, Кокос прав -- из равенства по модулю степеней не следует таковое для оснований.

Вася Пупкин 2013-01-12 02:15:15 пишет:
А, нет, Кокос, сорри -- поглядел на Ваш пример с кубами и семеркой, Вы, кажется, правы. Беру таймаут на обдумывание -- похоже, я и впрямь накосячил где-то в переходе.

Вася Пупкин 2013-01-12 02:01:11 пишет:
Тьфу, блин, смешал в ответе Зю для степеней и простого числа. Ну ладно, и так понятно.

Вася Пупкин 2013-01-12 01:58:51 пишет:
Кокос, во-первых -- таки да, естественно, все только для простых. Во-вторых -- таки да, естественно -- все по модулю, это подразумевалось у меня в тексте, и помодульность логики зануления не меняет(поэтому и для произвольного простого то же самое). В третьих -- Ваш "контрпример" таковым не является: для нечетной степени Зю зануление происходит только при равных помодулях, поэтому каждый помодуль запрещает только себя, а всего их таких и будет Зю, что Вы и показали -- то бишь, для кубов и тройки склеятся четыре числа. Если Вы к тому, что вот, мол, а вовсе не ((Зю-1)/2)+2) -- так я такого и не утверждал, эта формула -- для четных степеней, а для нечетных, понятное дело, Зю-1, все определяется тем, пары запрещаются, или единички. Ну, а в четвертых... ну ладно, правда уже надоели эти балеты. Извините, но правда ощущение какого-то постоянного продирания через волну какого-то "а вот я тебя еще вот так переболтаю, а теперь еще вот так". Я верю, что Вы не нарочно, но правда, не получается у меня поддерживать эту куртуазную беседу.

KoKos 2013-01-12 01:46:40 пишет:
Или, чтобы уж в корне пресечь кривотолки, ;)) пусть даже будет "расширеннококосная постановка". :))) Зю=7 и кубы. 0->0, 1->1, 2->1, 3->6, 4->1, 5->6, 6->6. Однако, во-первых, очевидно достаточно всего четырех чисел, а не пяти. ;))) Во-вторых, пары по модулю не играют - именно потому, что пары опять дадут Вам *требование* пяти чисел. И в третьих, чертовы терминаторы, как видим, порою эффективнее... ;)))

KoKos 2013-01-12 01:19:18 пишет:
Вася Пупкин, неее. :) Это Вы уже увлеклись. Нам ведь надо не "a^2 = b^2", а "a^2 = b^2 *по модулю Зю*" (о моей расширенной формулировке забудьте, мы говорим о конкретной задаче). Это именно то, о чем я и говорил. Вы обобщили задачу на произвольно выбранный Вами же частный случай (простое Зю). Это показалось Вам достаточно удобным, и я совершенно не намерен Вас за это порицать. Мне показалось достаточно удобным перебрать семь вариантов. Естественно, для сорока семи я бы уже призадумался. :))) \n\n
Но менее частным от этого Ваш случай не стал. Да, как видим, для Зю=7 в *нашей* задаче соблюдается правило: "a^2 = b^2 по модулю 7, когда a+b = 0 по модулю 7". Каковое позволяет Вам спокойно вычеркивать пары. Для произвольного простого Зю не проверял пока, может сейчас на выходных гляну (хоть это и нелюбимая мной алгебра :))). \n\n
Но и настоящим общим случаем Вы это называть таки не имеете права. ;))) Простой контрпример: Зю=3 и кубы. 0->0, 1->1, 2->2.

Вася Пупкин 2013-01-11 23:29:55 пишет:
И кстати, Админ -- насчет разлагаева в суммы-разности это тоже, пожалуй, лишняя пурга. Просто -- а в каких там случаях a^2 = b^2(или, в расширеннококосовой формулировке, a^n = b^n). Ответ -- либо при а=плюс-минус b(четные степени), либо просто a=b(нечетные). Ну, и дальше поехали вычеркивать однушки или пары, как и ран-ше.

Вася Пупкин 2013-01-11 10:09:31 пишет:
Кокос, болтология, я пас. Кстати, задача с кубами делается еще проще, чем с квадратами -- и именно тем же самым приемом. Про четвертые степени -- опять той же сложности, про пятые -- опять проще. Ну, и т.д., сами сообразите про общий вид для любых степеней.

KoKos 2013-01-08 22:16:26 пишет:
:)) Вася Пупкин, я не собираюсь оспаривать красоты Вашего решения. Но по сути оно ничем не отличается от остальных "чертовых терминаторов". 8) С тем же успехом можно спросить: "а если в условии будут не квадраты, а кубы?" ;) Не так ли? :))) Я никогда не устану утверждать, что лень есть двигатель прогресса. :) Каждый, включая Вас, просто ограничил разновозможные "если" пределами своей лени. Или, если хотите, - практичности. :)

Вася Пупкин 2013-01-08 20:51:49 пишет:
Вот же ж терминаторы чертовы. А если в условии будет не семь, а сорок семь -- вы возможные значения квадрата по модулю выписывать будете?

< 1 2 >

Добавьте комментарий:
Автор:

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Задача Квадрат 4x4:
не представился : [скрыто]
Задача Дефект масс:
R-2 : [скрыто]
Задача Некормленые марсиане:
jonson-72 : [решил задачу]
KoKos : [решил задачу]
Задача Опять собеседование в Яндекс:
не представился : [скрыто]
Задача Механика -2:
jonson-72 : [скрыто]
Задача Некормленые марсиане:
не представился : [решил задачу]
Задача Механика -2:
R-2 : [скрыто]
ivana2000 : [скрыто]
Задача 6-4=8:
не представился : [скрыто]
Задача Опять собеседование в Яндекс:
R-2 : [скрыто]
R-2 : [скрыто]
Данетка Новый глава:
Виталий : [задал вопрос]
Задача Почти игра в 12 палочек:
Виталий : [скрыто]
Задача Опять собеседование в Яндекс:
Виталий : [скрыто]



Реклама



© 2009-201x Логические задачи