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

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

Главная | О проекте | Все задачи-1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C | Добавить задачу



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

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

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





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


Задачи

Логические
Математические
С подвохом
Переправа
Переливания и взвешивания
Даты
Физика вокруг
Последовательности
Честные и лжецы
Слова и буквы
Теорвер, комбинаторика
Геометрические
Вопросы на эрудицию
Стратегии
Шахматы
Задания на наблюдательность
требуется помощь
Чисто поржать
Детские с подковыркой
Спички
Детективные
Ребусы / Шарады
Программистам
Вопросы к обсуждению


Данетки


Текущие:

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

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

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


Справочная



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


Реклама






задача: Бредовый инвариант

Задачу прислал: Вася Пупкин


Сложность: сложныеЕсть 2n положительных чисел, без повторений. Их разбили на два подмножества по n чисел в каждом. Отсортировали одно по возрастанию. А другое по убыванию. И дальше берут из каждого член номер k и смотрят их разницу по модулю. И суммируют эти разницы по всем этим парам. Доказать, что результат не зависит от разбиения.

+ 1 -


Ответ



А пес знает, самому только что рассказали, никаких идей.

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





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


ответов: 8

KoKos 2014-10-21 01:31:30 пишет:
А вот заданное условие тотальной положительности чисел - совершенно избыточно, на самом деле. Все то же самое верно для любых чисел без повторений, для которых не возникает вопросов с отношением "больше-меньше" и линейным раскрытием модуля. :) Даже повторения, по большому счету, можно допустить, - только будет куча "лишних" оговорок при выборе E и m. А вот комплексные числа уже так легко не отделаются, например... :)))
   Вася Пупкин: Лишнее, конечно. Но мне так рассказали.

KoKos 2014-10-21 01:18:33 пишет:
Добавлю только, на всякий, что сам по себе "экватор" не обязан принадлежать области определения множества и нужен нам лишь для наглядности. Он нам дает запись a[i] > E > b[i] для всех i от 1 до n, из которой, в свою очередь, автоматически и отщелкиваются все модули. :) То бишь, даже для множества {1,2,3,4} нецелый экватор 2.5 нас совершенно устроит.

KoKos 2014-10-21 00:54:37 пишет:
1. Существует "экватор" Е и единственное, с точностью до упорядочивания, разбиение, при котором все числа первого "верхнего" подмножества больше Е, а второго "нижнего" - меньше. Действительно, если мы все исходные числа отсортируем по возрастанию (например) и полученную последовательность е[1],...,e[n],e[n+1],...,e[2*n] разобьем посередине - то получим "верхнее" e[n+1],...,e[2*n] и "нижнее" е[n],...,e[1] соответственно. Наш потенциальный инвариант для этого случая будет выглядеть как простая поэлементная сумма "верхнего" минус сумма "нижнего".


2. Отметим также, что любые перестановки элементов внутри "верхнего" и/или "нижнего" подмножеств (но пока что НЕ между подмножествами) на результат не влияют - действительно, все модули будут всегда раскрываться на плюс "верхнее" число минус "нижнее" число, а от перестановки слагаемых сумма, как известно, не меняется. :)


3. Для любого другого упорядоченного разбиения исходного множества существует некое m такое, что n >= m >= 1, что первые m элементов (они все и только они) "верхнего" подмножества, обозначим их b[1],...,b[m] будут меньше Е - вследствие упорядоченности. Остальные элементы "верхнего" обозначим a[m+1],...,a[n] (да-да, те "бэ", а эти "а" ;))). Очевидно, что тогда первые же m элементов, и только они, "нижнего" подмножества a[1],...,a[m] окажутся у нас больше Е. И, аналогично, остальных "нижних" обзовем b[m+1],...,b[n]. Считаем наш потенциальный инвариант в этом случае: abs(b[1]-a[1])+ ... +abs(b[m]-a[m]) + abs(a[m+1]-b[m+1])+ ... +abs(a[n]-b[n]) = -(b[1]-a[1])- ... -(b[m]-a[m]) + (a[m+1]-b[m+1])+ ... +(a[n]-b[n]) = (a[1]-b[1])+ ... +(a[m]-b[m]) + (a[m+1]-b[m+1])+ ... +(a[n]-b[n]) = (a[1]+...+a[n]) - (b[1]+...+b[n]) - таки да, и правда выходит инвариант. Ибо a[1],...,a[n] есть ни что иное, как некоторая перестановка e[n+1],...,e[2*n] - а b[1],...,b[n] перестановка e[1],...,e[n] соответственно.
   Вася Пупкин:

K2 2014-10-20 09:18:53 пишет:
всего две шутки, в начале и наоборот в последних стоках - разве много? да и Другого решения всё-равно не было - издержки ленности вставлять картинку, вот и пришлось словами описывать то аццкое каля-маля (да, от картинки боюсь легче не стало бы) которое и навело кое как на верное (вроде как) направление, и угу, на кофе и молоко действительно получилось чем-то похоже в итоге. Тем что точно считать ничего НЕ надо, но достаточно только ухватить Главное... Спасибо - интересная была задачка.
   Вася Пупкин: Рад, что Вам понравилось. Не "чем-то похоже", а именно тем и -- если стаканы одинаковые, и смесей по стакану, то одного в другом столько же, сколько другого в одном. Это точно и есть про кофе и молоко, только, разве что, в нашем случае про воду и масло(ну и, для зануд, измененное на противоположное направление гравитации). Все остальные выкладки -- вообще, строгогря, лишние.

Вася Пупкин 2014-10-20 08:51:11 пишет:
Ага, нашел. Отсортируем все 2n чисел -- скажем, по убыванию. Теперь разделим отсортированное на n первых и n следующих. Ну, и обратим одну из половин. Это тоже разбиение. И пойдем парами хапать разности: самое большое из первого и самое малое из второго, потом поменьше из первого и побольше из второго, и т.д. По построению, все из первого больше всех из второго, поэтому все числа из первого войдут с плюсами, а все из второго -- с минусами. Назовем одни макси-числами, а другие -- мини-числами. Что будет, если теперь все перемешать, произвольно разделить на половины, и снова отсортировать? Если макси-число идет в паре с мини-числом, то, поскольку все берется по модулю, неважно, кто из пары где оказался -- в любом случае макси-число пойдет с плюсом, а мини -- с минусом. А вот может ли так случиться, что парой окажутся два макси, либо два мини-числа? Тогда бы одно из них поменяло знак вхождения. Вот и проверим. Для определенность будем рассматривать макси-пару, для мини рассуждение будет в точности то же. Итак, предположим, что и в первом, и во втором подмножествах(оба, напоминаю, мощности n), отсортированных одно по убыванию, а другое по возрастанию, на позиции p(позиции будем нумеровать от 0 до n-1) стоят макси-числа. Заметим, что все мини-числа также распиханы по двум этим подмножествам. А где они в них расположены? Поскольку все мини-числа по построению меньше любого макси -- они могут попасть в одном подмножестве только слева от позиции p(p позиций), а в другом -- только справа от _той_же_ позиции p(n-1-p позций). В сумме это дает ровно n-1 место для мини-чисел. Но ведь мини-чисел, по исходному построени -- n. Проклятая макси-пара украла одно место, размещение невозможно. Единственным предположением было существование макси-пары на позиции p. Понятно также, что если таких макси-пар не одна, ситуация только ухудшается -- не только за счет большего кол-ва позиций, отнятых макси-парами у мини-чисел, но и за счет того, что для них(мини-чисел) остается место лишь слева от крайней левой макси-позиции или справа от крайней правой таковой. Ну, вот, собственно, и все -- макси-пара невозможна, аналогично невозможна и мини-пара, сталть -- при любом разбиении все пары по-прежнему останутся смешанными(макси-мини), сталть -- все макси-числа по-прежнему идут с плюсом, а все мини -- с минусом, и результат таки действительно не зависит от разбиения.
   Вася Пупкин: Говно решение, хоть и работает. Правильный способ, без терминаторства -- см. у Вадима и К2.

K2 2014-10-19 22:36:30 пишет:
хмм... это я теперь что ли ещё и "пёс"?..

Вадим 2014-10-19 22:36:06 пишет:
прошу прощения за 2 прошлых сообщения. отчего-то не хочет добавлять весь текст..

   Вася Пупкин: Очень красиво, мне стыдно за свое. Похоже ма известную задачку про стакан кофе и стакан молока, в которых ложкой из одного в другой и обратно перекидывают. Конечно, в таком направлении и надо было.

K2 2014-10-17 12:41:26 пишет:
Будете смеяться (но и Саг`очка тоже умерла) - но кажется я порешал эту задачку Графически, точнее в картинках, не зря она "бредовая", итак... Берём и "подтасовываем" в Первое подмножество Эн бОльших значений, а во второе - эН мЕньших - почему нет? Мы - сатрапы = имеем право. И получаем некое значение = СУМ(мах) - СУМ(мин) - равное Чему-то, пускай будет ИКС. Дальше - берём по одному значению из подмножеств и меняем их местами (может это даже и Лишний шаг. но ради_красоты - пускай будет) - очевидно что оба "подменыша" займут Первые строчки в своих новых подмножествах, один - как заведомо наименьший, в списке отсортированном по Возрастанию, и вице верза - второй наибольший в поубывательном. И так как они стоят в списке друг напротив дружки, а вычитаем мы ПО МОДУЛЮ - то так же ясно что меняй не меняй, итоговая сумма останется тем же самым ИКС-ом. Ну и так сказать "фаталити" - берём Произвольно Перемешанные Перемешки - и смотрим - сколько в Первом списке у нас будет чисел из "минималистического" - если ноль или все - то очевидно (я не слишком злоупотребляю этим словом?) что сумма будет либо ИКС либо модуль-минус-икс, то есть всё равно - ИКС. Если же их Несколько то опять же очевидно что 1 - все остальные - "максималисты", 2 - во Втором списке "максималистов" Столько ЖЭ 3 - все "чужие" - занимают ВЕРХНИЕ "половины" сответствующих списков 4 - граница "разделения" списков где поменяется знак вычитания - пройдёт по этим же самым "границам чужих" В Списках - так как их одинаково а "там" напротив будут сидеть явно бОльшие ибо из "бОльшего Списка"... ну и всё?.. кто до сих пор не запутался тому уже Давно очевидно что колдуй баба, колдуй дед, но модуль на модуль - всё равно получим ИКС... и я бы даже сказал - сферический икс в вакууме. Спасибо за внимание...
   Вася Пупкин: Блин, К2, это, помнится, Вы меня как-то за много букв упрекали? Честно говоря -- жутко мешает читать это постоянное астраумие, из которого надо смысл выдирать... Я только прочитав решение Вадима, сумел въехать, что у Вас такое же.

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

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

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



 





Обсуждаем

  Задача Разрезанный треугольник:
http://lprobs.ru/img/yes.gif : [скрыто]
Гостевая книга:
не представился : Это было в 1913 году. Одиннадцатилетняя девочка, пансионерка Московской Ржевской гимназии очень прос...
Задача Гора.:
Xuzke : [скрыто]
Гостевая книга:
не представился : В школе все казалось правильным. Из математики следует физика, из физики следует химия, из химии сле...
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...



Реклама



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