Вход через социальные сети

  • 02.09.2017, 18:38
    1 up down
    Сообщение

    Если стоимость слитка может быть нулём (что-то вроде фальшивых слитков), то может оказатся. Пример - 239 слитков по 0 таллеров, 1 слиток по 360 таллеров.

     

    Если стоимость слитка всегда больше нуля, то не может оказатся.

     

    Разделить можно например используя следующий алгоритм.

    1) Разделим 240 слитков на две группы. В первой 120 каждый стоимостью 1, во второй 120 остальных.

    Замечание: из 240 как минимум найдётся 120 стоимостью 1. Экстремальный случай - 120 по 1, 120 по 2.

    2) Разделим вторую группу на две подгруппы по 60 и 60 (любым образом). Пусть суммарная стоимость в первой подгруппе x, во второй y, и x\geq y.

    Тогда x+y=240, т.е. оба числа имеют одинаковую чётность и следовательно x-y чётное.

    Так же y\geq 60, значит x=240-y\leq 240-60=180, значит x-y\leq 180-60=120.

    3) Перенесём из первой группы (где все по 1) во вторую подгруппу ровно x-y слитков.

    Теперь в первой подгруппе и во второй подгруппе суммарная стоимость одна и та же. В первой группе осталось какое-то чётное количество слитков (возможно 0).

    4) Теперь перенесем половину слитков из первой группы в первую подгруппу, а вторую половину во вторую подгруппу.

     

    Итог: мы разделили 240 слитков на две группы (в алгоритме "подгруппы") с равной суммарной стоимостью.

    Сообщение было отредактировано zykov в 02.09.2017, 18:38.