@mr96:
il 20 ti dice che i numeri da 1 a 100 sono stati scritti in un ordine sconosciuto. Per capire quest'ordine hai la possibilità di fare una serie di domande. L'unica domanda ammessa ti permette di sapere, scelti 50 numeri (da chi formula la domanda), l'ordine relativo tra questi. Quante domande sono sufficienti per capire l'esatto ordine di tutti i 100 i numeri?
il 17 dice: metto nella tabella tanti 1 quanti -1. Di ogni riga e ogni colonna prendo la somma in valore assoluto. Chiamo M il minimo di questi valori. Fissati gli 1 e i -1 M è fissato. Però se spostiamo 1 e -1 M può variare. Il problema ti chiede quanto può valere al massimo M (0 è il minimo...)
Esempio con una tabella 4x4 (1 = A; -1 = B)
AABB
AABB
BBAA
BBAA
Tutte le colonne e le righe hanno somma 0. M vale 0
AAAB
AAAA
ABBB
BBBB
Alcune righe, colonne hanno somma (in valore assoluto) 4, altre 2, altre 0. M vale 0
AAAB
AABA
ABBB
BABB
Tutte le colonne e le righe hanno somma 2 (in valore assoluto). M è 2
In effetti il più grande M possibile per una tabella 4x4 è proprio 2 (sarebbe da dimostrare, ma è così)
@Lasker:
il 19 l'ho cannato io, certo. Purtroppo gli ultimi li ho dovuti scegliere un po' di corsa e buttandoci quel problema non ho pensato (all'ovvio) caso particolare.
A mia parziale discolpa cose del genere capitano anche nelle gare a squadre vere (ok, magari non nel 19!), quindi diciamo quell'eventualità è stata simulata
I punteggi si bloccavano al primo risultato corretto, sì. Errore nostro, ma ormai la gara era iniziata e l'abbiamo lasciato così. Da tenere a mente per la prossima volta.
PS: il 19 però potreste provarlo a risolverlo in generale, ovvero dimostrare che quella somma è sempre 180°