코로나 바이러스 퍼즐 중지 [닫힘]
정사각형 영역 $2020 \times 2020 \text{ km}^2$ 로 나누어 $2020^2$세포. 일부 세포는 covid-19에 의해 오염됩니다 . 매주 바이러스는 최소한$2$오염 된 세포와 공통점. 감염된 세포의 최대 수를 찾아 어디에 위치 하든 covid-19 대유행이 전체 지역으로 퍼지지 않도록합니다.
학교 친구가 내게이 문제를 줬는데 (수수께끼라고하는 게 더 낫다) 봉쇄 기간 (7-8 월)에 있을지 모르지만 잊어 버렸고 어제 그는 문제를 해결할 수 있었는지 물었습니까? 그리고 그 시간과 어제, 그리고 오늘도 그 문제에 대해 충분한 노력을 기울 였지만, 대답은 분명하지 않았습니다. 주목 해 주셔서 감사합니다!
답변
주장 : $n$ 으로 $n$ 그리드 (보다 적은 경우) $n$ 사각형이 처음에 감염되면 감염이 전체 지역으로 퍼지지 않습니다.
으로 사각형의 모서리를 정의 프론티어 에지 가장자리의 일측 감염된하지만 다른 측면은 감염되지 않은 경우. (전체 외부 영역$n$ 으로 $n$ 그리드는 항상 감염되지 않은 것으로 간주됩니다.)
핵심 기본형 : 감염이 전파됨에 따라 경계 가장자리의 수는 결코 증가 할 수 없습니다.
핵심 기본형의 증거 : 감염이 새로운 사각형으로 확산 될 때마다 적어도 두 개의 인접 항목이 이미 감염된 것이므로 최소한 두 개의 경계 가장자리를 잃고 최대 두 개를 얻습니다. 증명의 끝.
주장의 증거 : 감염이 전체 지역으로 퍼졌다 고 가정합니다. 그 당시 국경 가장자리의 수는$4n$(보드의 전체 외부 가장자리). 핵심 기본형에 따르면 초기 경계 모서리의 수는 최소한$4n$. 따라서 적어도$n$초기 사각형이 감염되었습니다. 다른 말로하면$n$ 사각형이 처음에 감염되면 감염이 전체 지역으로 전파되지 않습니다.
(덧붙여서, 크기의 초기 구성이 많이 있습니다. $n$ 이로 인해 대각선뿐만 아니라 전체 보드가 감염됩니다.)