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

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




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

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

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





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


Задачи



Данетки


Текущие:

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

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

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


Справочная



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


Реклама






задача: Перестановка в матрице

Задачу прислал: Вадим Любимов


Сложность: сложныеДоказать, что любую перестановку элементов матрицы можно осуществить в три шага: сначала переставить элементы в строках, затем в столбцах, и опять в строках.



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



Ответ





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





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


ответов: 12

KoKos 2012-05-24 13:10:09 пишет:
Ваша задача - это та же "домашка". :) У меня постоянно находятся другие дела и я не могу выделить достаточное количество времени для того, чтобы засесть и решить ее. Включая проверку на ошибки. Возможно, на выходных я смогу преподнести Вам строгое решение.

KoKos 2012-05-24 13:06:55 пишет:
Вадим, не ссорьтесь. :) "то над чем именно Вы собирались "здорово повозиться"?" - именно над строгим доказательством и поиском собственных ошибок. Знаете, я в школе практически никогда не делал домашних заданий (уже много раз повторял, что я - лентяй). Но чтобы не нарываться на плохие оценки, я перед уроком просил у кого-нибудь списать "домашку". :))) Так вот, мне отдавали "домашки" на списывание чуть ли не наперебой и с удовольствием. Потому что я еще и находил и исправлял в них ошибки, если таковые имели место быть. :)))

Вадим Любимов 2012-05-24 12:42:51 пишет:
Теперь по-существу. Вы пишите: "Думаете не всегда будет работать жадный алгоритм? Пока проблем не вижу..." Вот Вам простой контр-пример (специально для Вас делаю матрицу квадратной :-], хотя с прямоугольной 3x4 было бы ещё проще).


Вадим Любимов 2012-05-24 11:36:04 пишет:
KoKos, я не просто говорю, что вы ещё не решили задачу, а указываю на конкретную подзадачу (выбор множества X), которая не решена. И дело даже не в том, что она у Вас ещё не решена, а что Вы уже допустили конкретные ошибки, которые я Вам чётко описал (1 - неправильная стратегия выбора X и 2 - неправильное доказательство существования X). Странно, однако, если Вы так были уверены, что Ваша жадная стратегия всегда работает (и до сих пор ещё, похоже, не можете в этом разубедиться:)), а также, что Ваш аргумент с "зю" правильный, то над чем именно Вы собирались "здорово повозиться"?? Ведь если посмотреть внимательно, Ваше доказательство вполне "строгое", с точностью до этих двух летальных ошибок, о которых Вы, судя по всему, не имели понятия до того, как я на них указал. Что же лично Вас смущало в Вашем доказательстве?

KoKos 2012-05-22 10:58:33 пишет:
Вадим, так ведь я и не говорил, что уже решил задачу - я начал с того, что это лишь идея и закончил тем, что надо повозиться. :) По Вашим вопросам: №1 - да. Формулировка такая, потому что она была призвана не только описать множество выбираемых элементов, но и сам алгоритм выбора :) так что №2 - тоже да. Хм... Думаете не всегда будет работать жадный алгоритм? Пока проблем не вижу, но если найду, прийдется его уточнить. Ну и №3 - конечно не обязана быть квадратной, но с квадратной матрицей рассуждать проще, а потом уже можно обобщить решение на прямоугольную - как Вы сами же и отметили.

Вадим Любимов 2012-05-22 06:48:53 пишет:
Bottom line: По сути дела, Вы сводите поставленную задачу выбора строковых и столбцевых перестановок к задаче выбора множества Х. И это хороший шаг в правильном направлении. Однако, последняя задача не намного легче первой, и Вы пока что её не решили.

Вадим Любимов 2012-05-22 06:44:50 пишет:
И ещё одно замечание. На самом деле, в общем случае, матрица должна быть прямоугольной. Но это не большая проблема: если есть правильное решение для квадратной матрицы, то его всегда можно модифицировать без усложнений для прямоугольной. Например, в Bашем решении, если размер матрицы NxM (N столбцов, M строк), то Х просто должно состоять из M элементов.

Вадим Любимов 2012-05-22 06:43:06 пишет:
Теперь о серьёзной проблеме. Если я Вас правильно понял по вопросу #1, то такое множество из N элементов (назовём его X) действительно всегда существует, и значит вторая часть Вашего доказательства правильная. Однако, существование и построение множества X, вообще говоря, далеко не очевидны. Мало того, что Вы не приводите ни какую конкретную стратегию выбора X, Ваше доказательство существования X с помощью элемента "зю" мне не выглядит правильным. Судя по отсутствию стратегии выбора X, вы предполагаете, что здесь будет работать "жадный алгоритм", т.е. что множество X можно построить поэлементно, заботясь при выборе очередного элемента лишь о том, чтобы уже выбранное подмножество удовлетворяло тому же критерию, что и всё множество X, не так ли? (Вопрос #2, да-нет). Если всё же нет, тогда приведите пожалуйста другую чёткую стратегию выбора X. Если да, то я готов с Вами поспорить, что такая "жадная" стратегия будет работать далеко не всегда.

Вадим Любимов 2012-05-22 06:40:55 пишет:
KoKos, в целом подход у Вас правильный, однако в первой части Вашего доказательства (которая заканчивается перед словом "Проецируем") есть серьёзная проблема (даже на идейном уровне :)). Прежде чем о ней говорить, хочу кое-что у Вас уточнить. Вы пишите: "Выбираем такие N элементов, что в конечной позиции они стоят в разных строках, но в начальной не стоят в одной строке (попарно)." Эта формулировка мне выглядит нечёткой. Судя по всему, Вы имели ввиду, что любые два из этих N элементов должны находиться разных строках, как в начальной так и в конечной позиции, не так ли? (Вопрос #1, да-нет) (Если да, то странно, что вы приводите две разные формулировки одного и того же условия выбора этих N элементов относительно начальной и в конечной позиций, да ещё и ставите между ними сбивающее с толку "но" :).)


KoKos 2012-05-18 13:34:30 пишет:
Вадим, не в качестве строгого доказательства, - но в качестве идеи. :) Решаем задачу с конца. Пусть у нас имеется квадратная матрица NхN. Выбираем такие N элементов, что в конечной позиции они стоят в разных строках, но в начальной не стоят в одной строке (попарно). Это всегда возможно - иначе некоторый элемент "зю" :) который должен вначале стоять в одной строке со всеми N элементами некоторой строки конечной позиции - тогда выходит, N+1 элементов на строку. "Проецируем" их все в первый столбец матрицы. Действие, обратное этой проекции и будет третьим шагом. Переставляем элементы первого столбца так, чтобы их строки соответствовали начальным - обратное действие есть второй шаг. Наконец, расставляем элементы по их начальным позициям в строках - обратное действие есть первый шаг. Все то же самое верно и для остальных "проекций" на остальные столбцы матрицы. Если же Вы требуете строгого доказательства, то с ним прийдется здорово повозиться. :)))

Вадим Любимов 2012-05-17 17:17:39 пишет:
KoKos, речь идёт об отдельных элементах. (Во-первых, иначе я бы написал "переставить строки/столбцы". А во-вторых, утверждение задачи было бы очевидно неверным. Ведь от перестановки целых строк или столбцов ни строковое ни столбцевое родство между элементами матрицы не меняется. А что если каким-то двум элементам захотелось стать (или перестать быть) родственниками? :))

KoKos 2012-05-17 12:40:19 пишет:
Хм? Вадим, уточните, пожалуйста - именно отдельные элементы, или *целые* строки и столбцы??? 8)

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

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

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



 





Обсуждаем

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



Реклама



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