Автор Тема: Олимпиада "Московский учитель" 2017  (Прочитано 24802 раз)

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #15 : 30.10.2017 02:40:16 »
Вообще, собственно говоря, математик выдающий подобные условия для задачи — профнепригоден.
Вынужден не согласиться. Задача математически довольно красивая. Проблема в том, что, скорее всего, организаторы олимпиады стащили её из какого-нибудь математического ВУЗа не воткнув как следует в доказательство. У них есть какой-то набросок этого доказательства и их "эксперты" пытаются сравнить этот набросок с ответами участников олимпиады. И когда "эксперты" видят другое доказательство, то они просто не могут понять, что оно тоже доказывает необходимое утверждение, т.к. совсем не похоже на то, что у них есть в ответе. Так же было и в прошлом году с одной программой - тут есть тема прошлогодняя по этому поводу.

Оффлайн stranger573

  • Мастер
  • ***
  • Сообщений: 1 434
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #16 : 30.10.2017 02:48:38 »
Я могу предложить число больше 19 (S>19). Это, например, S=37. И Вы не сможете привести частный случай
Да легко — разбиваем на число 0,1 и сколько там чисел меньше 1. В одной группе одно число 0,1 в другой в сумме 36,9 а это больше 19. Условия разбиения и распределения по группам не заданы, поэтому можно и так. А ещё можно в одной группе все слагаемые, а в другой ни одного.
« Последнее редактирование: 30.10.2017 02:52:31 от stranger573 »

Оффлайн stranger573

  • Мастер
  • ***
  • Сообщений: 1 434
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #17 : 30.10.2017 02:56:55 »
Фраза "каждое число" не равна фразе "уникальное число"
Вообще-то в этом случае равна. Ибо если у вас будет хотя бы два одинаковых числа и вы раскидаете их в разные группы — то одно и то же число будет в обоих группах.

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #18 : 30.10.2017 02:57:29 »
Условия разбиения и распределения по группам не заданы, поэтому можно и так. А ещё можно в одной группе все слагаемые, а в другой ни одного.
Условия распределения очень даже заданы:
Цитировать
эти числа можно разделить на две группы так, что каждое число попадает только в одну
группу и сумма чисел в каждой группе не превосходит 19.
И, если сумма чисел равна 36,9, то их можно разделить на две группы, учитывая и 0,1 так, чтобы сумма в обоих группах не превышала 19.

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #19 : 30.10.2017 03:00:41 »
Фраза "каждое число" не равна фразе "уникальное число"
Вообще-то в этом случае равна. Ибо если у вас будет хотя бы два одинаковых числа и вы раскидаете их в разные группы — то одно и то же число будет в обоих группах.
Вы неправильно поняли. Есть числа: x1, x2, x3 и т.д. Число x1 вполне может быть равно x2, но x1 не может присутствовать в двух группах. Эта фраза означает, что x1 может попасть только в одну из групп, но никак не в обе. То же касается и x2, которое вполне может быть равно x1

Оффлайн stranger573

  • Мастер
  • ***
  • Сообщений: 1 434
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #20 : 30.10.2017 03:07:54 »
Условия разбиения и распределения по группам не заданы, поэтому можно и так. А ещё можно в одной группе все слагаемые, а в другой ни одного.
Условия распределения очень даже заданы:
Цитировать
эти числа можно разделить на две группы так, что каждое число попадает только в одну
группу и сумма чисел в каждой группе не превосходит 19.
И, если сумма чисел равна 36,9, то их можно разделить на две группы, учитывая и 0,1 так, чтобы сумма в обоих группах не превышала 19.
А вот это уже не любое представление, а опять частное. Любое я вам привёл — в одной группе все, в другой ни одного.
А если считать, что на слагаемые можно разбивать любым способом, но для всех и каждого из них должен существовать хоть один способ разбиения на две группы когда каждая из них ≤19, тогда Smax=38.

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #21 : 30.10.2017 03:20:02 »
Условия разбиения и распределения по группам не заданы, поэтому можно и так. А ещё можно в одной группе все слагаемые, а в другой ни одного.
Условия распределения очень даже заданы:
Цитировать
эти числа можно разделить на две группы так, что каждое число попадает только в одну
группу и сумма чисел в каждой группе не превосходит 19.
И, если сумма чисел равна 36,9, то их можно разделить на две группы, учитывая и 0,1 так, чтобы сумма в обоих группах не превышала 19.
А вот это уже не любое представление, а опять частное. Любое я вам привёл — в одной группе все, в другой ни одного.
А если считать, что на слагаемые можно разбивать любым способом, но для всех и каждого из них должен существовать хоть один способ разбиения на две группы когда каждая из них ≤19, тогда Smax=38.
:-)
Это было бы отлично!
Но, повторюсь, условия достаточно чёткие и, сколько не изощряйся в формулировках, рамки довольно жёсткие.
Вы сейчас путаете два условия. Одно рамки раскрывает, а другое ограничивает.
Вот два слона этих рамок:
  • Любое разбиение S на слагаемые меньше 1
  • Есть возможность распределить на две группы
Так вот при S=38 НЕ любое разбиение позволит распределить слагаемые по группам, чтобы сумма групп была меньше 19.
При S=37 абсолютно любое разбиение позволит распределить.
Вам предоставляется воля в разбиении S, а вот в составлении групп воли у Вас нет. Группы составляются по определённому правилу. Если по этому правилу можно составить группы из любого разбиения S, то условие выполнено.
Так вот вопрос ещё раз. Можете ли Вы написать на какие слагаемые надо разбить 37, чтобы из этих слагаемых нельзя было бы составить две группы сумма которых не больше 19?
Зато я могу написать на какие слагаемые надо разбить 38, чтобы Вы никак не смогли распределить эти слагаемые на две группы так, чтобы сумма слагаемых в этих группах была не больше 19.

Оффлайн stranger573

  • Мастер
  • ***
  • Сообщений: 1 434
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #22 : 30.10.2017 03:38:26 »
Вы сейчас путаете два условия. Одно рамки раскрывает, а другое ограничивает.
Вот два слона этих рамок:
  • Любое разбиение S на слагаемые меньше 1
  • Есть возможность распределить на две группы
Вот поэтому я и говорю — условие недостаточно чёткое. Если условие требует семантического разбора — оно неоднозначно. Этим любые задачники просто кишат. Неважно где и как часто подобное встречается, это в само условие не входит и поэтому рассматриваться при решении не должно никоим образом. Условия должны быть однозначно понятны из самих условий только.

Зато я могу написать на какие слагаемые надо разбить 38, чтобы Вы никак не смогли распределить эти слагаемые на две группы так, чтобы сумма слагаемых в этих группах была не больше 19.
Напишите.

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #23 : 30.10.2017 03:46:40 »
Вы сейчас путаете два условия. Одно рамки раскрывает, а другое ограничивает.
Вот два слона этих рамок:
  • Любое разбиение S на слагаемые меньше 1
  • Есть возможность распределить на две группы
Вот поэтому я и говорю — условие недостаточно чёткое. Если условие требует семантического разбора — оно неоднозначно. Этим любые задачники просто кишат. Неважно где и как часто подобное встречается, это в само условие не входит и поэтому рассматриваться при решении не должно никоим образом. Условия должны быть однозначно понятны из самих условий только.
Тут спорить не буду. Я по образованию математик и мне это условие представлено абсолютно чётким и однозначным.
Зато я могу написать на какие слагаемые надо разбить 38, чтобы Вы никак не смогли распределить эти слагаемые на две группы так, чтобы сумма слагаемых в этих группах была не больше 19.
Напишите.
Ну, например, разбить число 38 на 39 слагаемых каждое из которых равно 38/39.

Оффлайн stranger573

  • Мастер
  • ***
  • Сообщений: 1 434
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #24 : 30.10.2017 04:27:44 »
Уже сам увидел, в общем случае (для любого из максимальных значений группы и слагаемого) наихудший случай будет при разбиении на минимальное нечётное количество равных слагаемых. Надо подумать как это решить в общем случае.

Оффлайн stranger573

  • Мастер
  • ***
  • Сообщений: 1 434
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #25 : 30.10.2017 07:46:11 »
Решение в общем случае:

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #26 : 30.10.2017 08:40:24 »
Решение в общем случае:
Спасибо, Кэп!  ;-D
Это ведь шутка? Или серьёзно?
« Последнее редактирование: 30.10.2017 08:47:18 от tema »

Оффлайн Paver

  • Давно тут
  • **
  • Сообщений: 188
Re: Олимпиада "Московский учитель" 2017
« Ответ #27 : 30.10.2017 09:08:11 »
Не погружаясь глубоко в тему, могу сказать, что до решения Темы (сори за каламбур) можно докопаться.
1. Почему, собственно, "Для поиска максимального числа, необходимо..." заполнить группу G1 именно так?
2. Условие G1 + x(k+1) явно некорректно. К G1 нужно добавлять именно что любое x из оставшихся, т.е. правильнее минимальное из них - x(n)
Предположение, что S не может быть больше 37,05 - доказано. Что это максимум - имхо нет.

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #28 : 30.10.2017 09:17:54 »
1. Почему, собственно, "Для поиска максимального числа, необходимо..." заполнить группу G1 именно так?
Всё очень просто. Вторая группа у нас, предположим, максимум, т.е. 19. Значит надо найти только ограничение первой группы. А для поиска максимального нужно сложить именно наибольшие элементы.
2. Условие G1 + x(k+1) явно некорректно. К G1 нужно добавлять именно что любое x из оставшихся, т.е. правильнее минимальное из них - x(n)
Дело в том, что это не условие. Это ограничение заполнения. Мы первую группу составляем из суммы наибольших из упорядоченного ряда до тех пор, пока не выполнится это ограничение. Условие тут не ставится.

Оффлайн tema

  • alt linux team
  • ***
  • Сообщений: 2 073
    • Email
Re: Олимпиада "Московский учитель" 2017
« Ответ #29 : 30.10.2017 09:29:49 »
Предположение, что S не может быть больше 37,05 - доказано. Что это максимум - имхо нет.
Предположим, что я угадал это 37,05. Там в конце написано, что 20*37,05/39=19. Т.е. S=37,05 число подходящее. Совершенно очевидно, что если S не может быть больше 37,05, а самим 37,05 может быть, то это и есть максимум...