Problema saptamanii - Vanatori (Solutie)

Cosmin Negruseri
01 noiembrie 2008

Problema Vanatori a fost rezolvata corect de Delia David, Ovidiu Gheorghioiu, Bogdan Dumitru, Dobrota Valentin-Eugen si Catalin Tiseanu.

Incercarea unor cazuri pe foaie duce la intuitia ca numarul maxim de vanatori este 4. Sa vedem de ce aceasta intuitie este adevarata. Orice vanator ce e intr-un punct (x, y) ce apartine uneia dintre cele patru clase x - par, y - par; x - par, y - impar; x - impar, y - par si x - impar, y - impar. Orice doua puncte din aceiasi clasa sunt unite de un segment ce are mijlocul intr-un punct de coordonate intregi. Astfel am demonstrat ca putem numarul maxim de vanatori este 4, cate unul corespunzator fiecarei clase.

Ovidiu a venit cu generalizarea la spatiu n dimensional unde numarul maxim de vanatori e 2ⁿ. M-a si intrebat daca nu ar fi restrictia ce cerea ca trei vanatori sa nu fie colineari care e numarul maxim de vanatori care pot fi pusi pe grila. Eu naiv i-am zis ca pot fi pusi o infinitate, si Ovi mi-a raspuns ca sunt mai putin de 6 miliarde de oameni cu permis de port arma, deci numarul maxim clar nu e o infinitate ;).