задача на числа

[tennisru]

В каждой строке квадратной таблицы написано по числу. Известно, что в каждой строке таблицы сумма двух наибольших чисел равна А, а в каждом столбце таблицы сумма двух наибольших чисел равна Б. Докажите, что А=Б

верно ли мое решение ?.
Решение: возьмем два максимальных числа в столбце, приэтом в других столбцах на этих строчках может быть только одно максимальное число в этом столбце.



главное ,что два максимальных числа взятых в каждом столбце не могут располагаться на одной строке более чем 2 раза (не знаю доказать почему это так). То есть при сумме в строке будут скалдываться теже числа, что и в столбце.значит А=Б.

[MrDindows]

Всё как-то стрёмно, и , походу, не верно)
По крайней мере в вашем доказательстве нету ни слова об одинаковых суммах=)

Почему-то мне кажется что здесь можно воспользоваться индукцией)

[tennisru]

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

[MrDindows]

У вас какое-то неправильное представление о максимальных числах.
Вы их отмечаете точками, выделяете, буд-то бы они какие-то рыжие)

Забудь-те слово максимальные, оно вообще слегка не в тему в этой задаче.
Давайте лучше будем говорить "наибольшие".
Мы берём из СТРОКИ ( или СТОЛБЦА) два наибольших числа.
Учтите, что если некое число - наибольшее в СТРОКЕ, то оно НЕ обязано быть наибольшим в СТОЛБЦЕ.

И если и будете помечать как-то наибольшие числа в таблице, то лучше называйте их буквами, либо используйте ДВА разных типа пометок: один для чисел, наибольших в своих строках, второй - для чисел, наибольших в своих столбцах.

[tennisru]

некоректно сформулировал вопрос, отредактировал

[Ian]

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

[quote=]
This is a rather cheap counterexample, however. If , the statement is correct.

[/quote]

[СергейП]

Source of the post работают люди, не то что здеся

Не, здеся тоже работают.
Но чо писать, если неча

Сразу пришла мысля, что утверждение неверно, пробовал контрпример строить.
Подобный прямоугольник легко строить, можно взять 2, приставить уголком, один aXb, другой bXa. Но проблема в том, что если строк больше столбцов, то можно получить большие суммы по строкам, а по столбцам нельзя. Так что, искомое утверждение, похоже, верно.

[kik]

Неа, здесь всё не так прозрачно.

Во-первых, задачу нужно поставить более строго.
В любом конечном множестве чисел может быть только одно наибольшее (или назовите его хоть максимальным) число. Поэтому, нужно подразумевать, что мы берем в каждом столбце и в каждой строке наибольшее число, т.е. например в i-м столбце: номер строки j₁: a_ij1=max_j(a_ij).
Второе "наибольшее" в том же столбце это a_ij2=max_j(a_ij), j₂<>j₁.
(Что-то сложности с индексом у индекса, и в тексте, и в Math)
И вот теперь можно начинать что-то делать
(можно ослабить условие, неравенства сделать нестрогими, т.е. допустить что либо оба "наибольших" числа равны, либо второе из них равно хотя бы еще одному числу из столбца. Эти случаи дают свободу в выборе индекса. Но если докажем самый строгий вариант, то там все будет совсем просто)
А никакого во-вторых пока нет. Слова "ну тут всё довольно очевидно" не принимаются, выкладки в студию


Есть один из самых простых вариантов: это случай, когда в таблице есть строки i₁, i₂, столбцы j₁, j₂, такие, что на их пересечениях стоят числа a,b,c,d, и для них по условию: a+b=A, c+d=A, a+c=B, a+d=B. В одно действие показываем что A=B и никак иначе.
В остальных же случаях нужны более хитрые действия.

[СергейП]

Да просто всё здесь.
Предположим, что суммы по столбцам В не равны суммам по строкам А, допустим В>А.
Теперь заметим, что перестановка столбцов (и строк) ничего не меняет. Отсортируем столбцы в порядке убывания максимальных элементов столбцов. Максимальный элемент в последнем столбце не меньше В/2 (иначе В не получить). Тогда все эти максимальные элементы столбцов расположены в разных строках, иначе в какой-то строке сумма 2-х элементов будет не меньше В, сумма 2-х максимальных по строке также будет не меньше В, т.е. больше А, что невозможно. Но тогда эти максимумы займут все строки. Следовательно, 2-ой по величине элемент последнего столбца будет располагаться в строке, где уже есть максимум какого-то столбца, в сумме они дадут больше А, что невозможно.