Это форум для общения шахматистов и размещения информации, имеющей отношение к шахматам в Воронежской области
Приветствуется участие шахматистов других регионов и информация, касающаяся шахмат вообще, Воронежской области, города Воронежа и близких тем

Финал чемпионата Воронежской области-2021 Второй дивизион Женщины
Юниорские первенства области-2021 Классика Рапид Блиц
Первенство областного шахматного клуба Высшая лига Первая лига
V летняя Спартакиада молодёжи, II этап (ЦФО) 18-23 Первенство Воронежа среди школьников Воронежский областной этап Белой Ладьи-2021
Чемпионат области среди женщин Чемпионат области среди ветеранов Чемпионат области по блицу первая лига высшая лига Мемориал Загоровского быстрые шахматы блиц Чемпионат области по шахматам Чемпионат области по быстрым шахматам высшая лига первая лига
Воронежская шахматная команда (с подтверждёнными никами) на lichess Проект Патиум (PostOrion) ВКонтакте
Воронежский онлайн-турнир в честь начала весны Турнир Voronezh Chess Team на lichess к Международному дню шахмат Онлайн-чемпионат Европы на chess.com Полная информация

Шахматные новости: Telegram-канал о шахматах в Воронежской области Спорт-Игрок РИА Воронеж ЦСП СК ВО Борисоглебская ДЮСШ Шахматы в Россоши Шахматы. Новая Усмань Клуб "Дебют" СОШ №101 Клуб "Эндшпиль" Лицея №4 Нововоронежский ДДТ Труд-Черноземье
Шахматные организации: FIDE ФШР МШФ ЦФО Областной шахматный клуб СШОР №13 ICCF РАЗШ: форум сайт
Шахсекция ВКонтакте "Воронеж шахматный" на БВФ Cтарый форум (только чтение) Старый сайт областной ШФ Старый сайт Воронежского фестиваля
Воронежская область в базе соревнований РШФ: Турниры Шахматисты
Соседи: Липецк Елец Белгород Алексеевка Урюпинск Балашов Тамбов Мичуринск Курск Железногорск

Воронежский шахматный форум

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



PuzzleUp

Сообщений 91 страница 101 из 101

91

Holmes написал(а):

№3 не решил

Вот решение третьей задачи.
16 тестов, 30 заданий, каждое задание входит в 8 тестов, в каждом тесте 15 заданий.
Задания по горизонтали, тесты по вертикали, 1 - задание входит в тест, 0 - не входит.
15 пар заданий, внутри одной пары по задания не пересекаются по тестам, а с любым заданием любой другой пары пересекаются ровно по 4 тестам.
Таким образом, решение обладает своеобразной симметрией.

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

Код:
1111111100000000
0000000011111111
0000111111110000
1111000000001111
1111000011110000
0000111100001111
1100001111000011
0011110000111100
1100001100111100
0011110011000011
1100110011001100
0011001100110011
1100110000110011
0011001111001100
1001100110011001
0110011001100110
1001100101100110
0110011010011001
1001011001101001
0110100110010110
1001011010010110
0110100101101001
1010101010101010
0101010101010101
1010010110100101
0101101001011010
1010101001010101
0101010110101010
1010010101011010
0101101010100101

0

92

Красиво! Но доказательства минимальности нет?

0

93

Holmes написал(а):

Но доказательства минимальности нет?

Строгого доказательства нет. Хотя алгоритм построен так, что на каждом шаге он он покрывает очередным заданием максимально возможное число оставшихся непокрытыми на данный момент четверок тестов.

0

94

Объявлен сезон 2021

10 задач, каждая на неделю, начало 1 сентября

+1

95

Начало завтра
Надеемся на участие троих воронежцев и на то, что хотя бы кто-то из нас попадет в десятку

=====

Puzzleup 2021 will commence on the 1st of September 2021 at 11:00 (GMT)
The competition will last 10 weeks, and every week a question prepared by Emrehan Halici will be posted on wwwpuzzleup.com website
We invite puzzle lovers all over the world to our online PuzzleUp competition
Best luck to all

0

96

Приветствую, друзья! Давно не участвовал в турнире, надеюсь в этом году хватит сил и времени пройти его до конца.
Я хоть и не воронежец, но желаю всем удачи в этой партии)
Давайте разместим несколько триколоров в первой десятке!

+2

97

Появилась первая таблица результатов за 2021 год

Результаты, там, правда, довольно однообразные
Видимо, наиболее трудные задачи не попали в отображаемую выборку, и сейчас в таблице дележ с первого места аж по сорок первое
В этом дележе только двое россиян, оба воронежцы - Sergey Shtyka и Dmitry Borisenkov
Остальным желаем успеха в решении не попавших в выборку задач, которые, очевидно, и определят итоговые места

0

98

Опубликованы предварительные результаты

Первое место разделили 10 участников, и среди них воронежец Сергей Штыка!
Ура!
Наши поздравления!

Мне же, надеюсь, удастся удержаться в 50 лучших
Других россиян в опубликованной таблице нет

Интересно было бы, если бы Сергей рассказал решение 8-й задачи
Ответ достаточно неожиданный

(Про 9-ю - не так интересно, там я долго решал задачу с неправильным условием, не обратив вовремя внимание на внесенное изменение, и потом уже не было настроения решать заново)

0

99

xuser написал(а):

Наши поздравления!

Спасибо!
Кажется, наоборот, в восьмой поменяли условие. Там сначала предлагалось найти (всего лишь) число Рамсея R(3,3,3,3), тогда как в википедии Числа Рамсея написано, что известны значения лишь двух многоцветных (число цветов > 2) чисел Рамсея, а именно, R(3, 3, 3) = 17 и R(3, 3, 4) = 30. После изменения условия (нет вершин с ребрами всех четырех цветов) как раз из R(3, 3, 3) = 17 стала понятна нижняя оценка задачи 8: можно совсем не пользоваться четвертым цветом (раскраска есть в этой же статье вики), раскрасить K16 в три цвета, и условия задачи выполнятся. Эту оценку я и отправил, доказательства, что нельзя больше, у меня нет. Опять две задачи из разряда нерешенных проблем  :O А в девятой удалось просто найти статью про проблему двух фальшивых монет, где приведен факт существования алгоритма за 8 взвешиваний, самого алгоритма нет.

0

100

Да, конечно, я перепутал номера задач, имел в виду задачу со взвешиваниями
Ссылка на утверждение, что 8 взвешиваний хватит, тоже была бы интересна, но алгоритм, конечно, интересней :-)

0

101

Статья
В статье, правда, рассматривается задача найти две фальшивые монеты, тяжелые или легкие - неизвестно, но не требуется определить, какие именно, тяжелые они или легкие. Не знаю, существенно ли это, пришлось предположить, что для больших n нет. Из таблицы 1 следует, что 8 взвешиваний хватает даже для n<=81. Возможно, что в процессе доказательства там конструируется и алгоритм, но я, конечно, не стал вникать - там зубодробительная математика пошла. По-прежнему не понимаю, зачем давать такие задачи.

+1

Быстрый ответ

Напишите ваше сообщение и нажмите «Отправить»