Problema de combinação baseado em algoritmo estilo IMO [duplicado]

Jan 03 2021

O problema é descrito na imagem, a solução deve ser uma prova construtiva, então você precisa encontrar um algoritmo que funcione independentemente de coisas como o tempo de execução. Qualquer ajuda seria desagradável. Não consigo resolver isso e estou tentando por um tempo

EDIT: Minha direção principal foi mudar o sinal em cada raw com soma negativa, agora cada raw está completo e a soma de todas as entradas é não negativa (uma vez que a soma de todos os raws agora é não negativa)

Respostas

1 quasi Jan 03 2021 at 15:30

Se alguma linha ou coluna tiver uma soma negativa, escolha uma e inverta os sinais.

Repita o processo.

Após cada transição, a soma de todas as entradas na matriz é aumentada.

Mas o valor absoluto das entradas permanece inalterado, portanto, há apenas possibilidades finitas para a soma total.

Segue-se que o processo acabará eventualmente.

1 AryanHemmati Jan 03 2021 at 15:33

Basta usar o seguinte algoritmo simples: Em cada turno, inverta os sinais de uma linha ou coluna aleatória com soma negativa e vamos provar que este procedimento termina em movimentos finitos: Observe que usando este algoritmo a soma dos números em todos os o tabuleiro sempre aumentará e como essa soma é limitada de cima e também existem possibilidades finitas para essa soma, nosso algoritmo irá parar em algum lugar e aí está o ponto que a soma de todas as linhas e colunas são não negativas.