Кому дать, кому дать, кому голову сломать?))
Конкурсы, олимпиады и головоломкиКлетчатое поле 5*5 (см. под катом картинку, не могу масштабировать). Расставьте в нем 13 крестиков так, чтобы я не смогла их зачеркнуть 3 горизонтальными и 3 вертикальными линиями (всего у меня 6 линий).
Юлия
А она решаема? 3 вертикальными и горизонтальными линиями можно зачеркнуть 21 крестик из 25.
11.03.2019
Ответить
Мумзелька 
вроде проверила. но я в последнее время тупое. надо за мной проверять.
если ошибок не найдется, то расскажу алгоритм.
вроде проверила. но я в последнее время тупое. надо за мной проверять.
если ошибок не найдется, то расскажу алгоритм.
10.03.2019
Ответить
Ирина
Вроде не получается зачеркнуть.
Буду очень благодарна, если расскажете принцип.
10.03.2019
Ответить
Мумзелька
для удобства занумеруем строчки и столбцы начиная с левого верхнего угла.
в задачке требуется найти какой-нибудь пример ( а не все возможные, хотя, есть ощущение, что любая другая комбинация получается из этой перестановкой строчек и выбором "первого" столбца. но чтобы строго доказать что других нет, надо рассмотреть невозможность иных комбинаций крестиков , чем 3-3-3-2-2. ( это я делать не пыталась).
интуитивно понятно, что не стоит ставить в строчку или столбец более трех крестиков. так мы упрощаем "вычеркивание".
так как строчки на самом деле равносильны, то сделаем в трех верхних по три. в двух нижних по 2
для удобства рисуем в первой строчке три крестике подряд.
что важно в этой задачке?
перебирать системно
какой принцип использовала я для первых трех строчек? - вторая и третья имеют по два совпадения с первой и отличающийся элемент различен.
какие еще могли бы быть варианты для перебора? ( глупые типа все совпадения специально не упоминаю)
а) два совпадения и третий одинаков
б) вторая строчка имеет одно совпадение с первой - при этом третья имеет либо по два совпадения с каждой, либо одно с одной и две с другими.
( все эти варианты я не перебирала. но стала бы, если бы в первом случае не получилось бы.)
В том случае, который перебирала я, какие варианты могли быть для 4 и пятой строчки.
в первый столбец ставить нельзя. поэтому варианты по столбцам
23 45
24 35
25 34
я перебрала их все. подошел только третий. ( следовало бы догадаться, что картинка симметрична в базовом варианте)
10.03.2019
Ответить
Ирина
Уф! Без бутылки не поймешь) Завтра сяду на живом примере осмысливать))
Спасибо!
P.S. Кроме примера ниже я видела еще одно решение, внешне все выглядят по-разному, но принцип 3-3-3-2-2 соблюдается у всех. Муж про этот принцип догадался, но расставить не получалось)
11.03.2019
Ответить
Мумзелька
Пример снизу с большой долей вероятности получается из моего перестановкой строчек и назначением главного столбца. Проверить могу потом из дома. Тут ключевое - перебор должен быть системным, чтобы не перебирать одни и те же (получаемые перестановкой) варианты
11.03.2019
Ответить
Мумзелька 
строчки с учетом перестановки ( как решение снизу преобразовать в мое).
все остальные перестановки тоже будут решениями
строчки с учетом перестановки ( как решение снизу преобразовать в мое).
все остальные перестановки тоже будут решениями
11.03.2019
Ответить
точно нельзя зачеркнуть？
да уж, головоломки......
