저거 이번 서울과학고 2차 시험문제 아닌가요?

문제1번

모두 바이러스에 감염된다.

1번째,2번째는 했고 좌표로 3번째 감염칸을 설명하겠다.

(1,3),(3,1),(4,2),(5,3)

4번째 감염칸은 (5,2),(3,1)

5번째 감염칸은 (5,1),(2,1)

6번째 감염칸은 (1,1)이다.

 

문제 2번

답:5개

바이러스가 있는 시작 위치:(1,5),(1,2),(3,1),(3,3),(5,1)

 

 

처음이여서 문제 2번은 표를 계속 그려서 풀었는데 그렇게 풀어도 되나요?

문제 2번 

타일의 위치에 상관없이 모두 감염이 되려고 할 때 필요한 감염 타일의 수를 구하자. 대각선 방향으로 2개 감염이 되어 있을 때 다른 타일이 감염이 된다. 타일의 위치가 어떻든 모두 감염이되는 최소 개수를 구해야 하므로 대각선 방향으로 최대한 놓여있지 않게 배치하자. 일직선으로 배치하는 것을 한 줄씩 띄고 계속 반복하면 이 타일들로 인해 새로 감염되는 타일은 없다. 이제 감염된 줄 사이에 타일을 놓을 차례인데, 어디에 놓든 그 줄의 모든 타일은 감염된다. 각 줄마다 하나씩 감염된 타일을 놓자. 

그러면 타일의 총 개수는    = 이다.  (단,[x]는 x 이하의 최소인 정수)

글 처음 써보는 거라서 오류가 많을 수 있어요. 오류가 있으면 지적 부탁드립니다!

바이러스가 바이러스가 전염되지 않는다는것을 밝히면 될것 같네요.

n-1개의 바이러스가 직또는 정사각형모양으로 배열되어있을 경우, 또는 한줄에 쭉 배열되어있을 경우 바이러스는 절대 다른칸으로 감염되지 않는다는것은 알겠는데....

1번문제는 모두 감염되지 않습니다.

왜냐하면 n이1이면 불가능하기 때문입니다.

n이 2나 3이어도 불가능합니다.

2번은 n개입니다. 왜냐하면 대각선으로만 바이러스가 있으면 되기 때문입니다.

그래도1번은 불가능합니다.

최소기 n개이기 때문입니다.

1번에 대해서는 n-1개이므로 가로줄만 따졌을 때 바이러스가 없는 줄이 생길텐데 그 없는 줄이 가(끝)에 있다면 그 줄의 모든 지점은 바이러스와 맞닿아 있는 변이 최대 하나밖에 없겠네요

아직 중간에 있을 때는 생각을 못해봤습니다.

1번문제 안돼요.그런데 이유를 잘 모르겠어요.

 

1번 답입니다. 세균의 감염된 칸의 둘레의 길이가 칸이 점점더 감염될수록 둘레의 길이가 같거나 줄어든다는 것을 이용하여 풀면 될 것 같습니다.

 

2번 문제는 n(n-1)일 때 안되는 예가 있으므로 n(n-1)+1일 때 무조건 모두 감염된다는 것을 보이면 될 것 같습니다.

제가 이 문제를 풀어드리죠. 바이러스에 감염되려면 4개의 변 중 2개 이상 감염된 칸과 맞닿아 있어야 합니다. 즉, 바이러스에 감염된 칸이 하나 늘어날때마다 바이러스에 감염된 칸의 전체 둘레는 줄어들면 줄어들지 절대로 증가하지는 않는다는 겁니다.(감염된 칸이 그전에 n개의 변에서 감염된 칸과 맞닿아 있었다고 합시다. 감염된 후에는 둘레가 n만큼 감소하고 4-n만큼 증가하지요. 전체 증가량은 4-2n입니다. 그런데 n은 2보다 크거나 같으므로 전체 둘레는 시간이 지나면 줄어들거나 같아야 합니다.) 자, 문제로 돌아와서 n-1개의 칸이 초기에 감염되 있었으면 둘레가 길어봤자 4(n-1)입니다. 그런데 n^2칸이 감염되었을 때 둘레는 4n입니다. 둘레가 증가했네요! 따라서 불가능합니다. 2번 문제는 서로 둘레가 맞닿아 있지 않은 n개의 칸이 감염되 있었으면 됩니다. 전형적인 단조성 문제네요. 비슷한 문제로는 이런 것도 있습니다.

Q. 칠판에 몇 개의 자연수가 적혀있다. 서로 다른 두 수를 골라 지우고 대신에 지운 두 수의 최대공약수와 최소공배수를 적을 때 이 작업은 유한 번 안에 끝남(변화가 없게 됨)을 보여라.

2번 문제가 성립되는 조건은 좀 까다로울 것 같습니다. 처음에 감염되지 않은 모든 타일에서 최대한 변 2개까지만 감염된 칸과 맞닿는 것이 가능합니다. 그 후도 마찬가지이고요.

가장 간단한 예가 '태현' 님이 찾으신 예거든요.(좌우대칭으로도 가능합니다) 근데 다른 예가 안 찾아지네요...

이래저래 고민을 좀 해봤는데 각 행과 열에 바이러스에 감염된 타일이 1개만 있으면 가능할 것 같아요. 어떻게 생각하시나요?(사실 근거가 없는 건 맞습니다....)

그런데 2번을 조금 바꿔서 바이러스의 위치를 처음에 정할수있으면 최소 몇개의 바이러스에 감염된 칸이 필요한지 증명할수 있을까요?

제 생각엔 n개일 것 같은데.

문제2 답은 n(n-1)+1 입니다.

단순하게 생각하면 쉽습니다.

감염이 되지않는 최악의 경우를 봅시다.

둘레를 최소화 하기위해, 정사각형의 모양을 띨 것입니다.

중앙에 n-2를 변으로 하는 바이러스로 이루어진 정사각형이 존재한다고 가정합시다.

그러면 그 이후에 감염은 이루어 지지 않기 때문에,

더 많은 초기의 바이러스가 필요합니다.

1개를 늘린다고 해보겠습니다.

이 경우 바이러스를 늘린구간에 변을 다 채우지도 못합니다.

그럼 이상태가 현재까지는 최악의 경우이겠네요.

다 채울 수 없기 때문에 1개의 블럭을 더 사용해보도록 하겠습니다.

방금 추가한 변의 이웃한 변에 추가해보겠습니다.

그쪽변을 한 꼭짓점 남기고 다 못채울 것입니다.

지금 상태는 (n-1)²인 정사각형의 바이러스 타일이 존재하는 상태입니다.

더 진전이 없기에 이 상태에서 하나를 더추가해보겠습니다.

바이러스 정사각형에 닿지않는 블럭이 아닌 다른 블럭에 하게될 경우,

한변은 온전히 살아 있는 상태가 됩니다.

이 상태가 문제의 답에 가까운 n(n-1)입니다.

만약 하나의 타일을 더 추가한다고 하면,

어느곳에서든 한변 전체를 채울 수 있게 됩니다.

이제 문제가 끝났습니다.

답은 n(n-1)+1이 나오네요.

조금 더 간결하고 수학적으로 증명하자면,

n(n-1)의 둘레의 길이는 최소 4n-2인데,

하나의 블럭을 추가하게되면 4n+1이니까,

앞서 1번의 증명에 의거하여 4n이 넘기때문이에 답은 .....이다, 도 가능하네요.

1번문제

n-1개로는 절~~대 모두 감염시킬 수 없습니다. n^2개의 타일을 가장 적은 타일로 감염시키기 위해서는 n^2개의 타일이 있는 도형의 한 꼭짓점으로부터 대각선으로 반대편 꼭짓점으로 가로질르는 선에 모두 바이러스가 있어야합니다. 그렇기 때문에 n-1개가 아닌 n개가 필요합니다.

증명과정

1개가 있을때는 1개로 채워집니다.

O

2개가 있을때는 최소 개수가 1번의 대각선 위치에 있는 위치에 하나가 더 있어야 합니다. 이렇게 말이죠.

O
	O

3개가 있을때는 이것의 대각선인 위치에 하나가 더 있어야합니다.

O
	O
		O

우리는 한가지 사실을 발견할 수 있습니다. 바로 n^2개는 (n-1)^2에서의 모양에서 겉부분을 한 겹 두르기만 한 것이기 때문에 하나가 더 필요합니다. 즉 다음 수식이 성립합니다.

n^2에 필요한 바이러스 수=n개/ 즉 n-1개로 채울 수 있다는 것은 절~~대 불가능합니다.

2번 n(n-1)+1

사실 위 댓글을 보면 이게 답이라는 것이 거의 확실하나 수학적인 증명이 부족했습니다.

그 증명을 해보려고 하는데요.

먼저 블럭이 1일때 최소둘레, 2일때 최소 둘레 ......을 나열했습니다.

1 2 3 4 5   6   7   8   9   10 ...

4 6 8 8 10 10 12 12 12 14 .....

1턴에 +2, 1턴에 +2, 2턴에 +2, 2턴에 +2, 3턴에 +2...

이라는 규칙을 발견할 수 있었는데,

그 이유는 직사각형에서 하나를 추가하게되면 2만큼 둘레의 길이가 늘어나지만, 다시 정사각형 또는 직사각형으로 돌아갈 때까지는 둘레의길이는 일정하기때문입니다.

+2를 할 때까지 기다리는 턴을 나열하면

1122233445566.....

이 됩니다(이 수 하나 하나를 각각의 쉼기간이라고 합시다.)

앞서 1번 증명에 따르면 감염이 시작되었을때 둘레의길이는 절대로 늘어나지 않기 때문에,

n(n-1)+1은 n²과 같은 쉼기간에 위치해야하고

n(n-1)은 한 쉼기간 앞에 위치해야 합니다.

일단 n²이 위치하는 쉼기간을 구해야합니다.

쉼기간을 같은 숫자끼리 더해주면,

2 4 6 8 10.....

이 됩니다.

그런데 제곱수의 차이는 1 3 5 7 9...입니다.

제곱수를 9라 가정합시다.

2 4를 빼면 3이남습니다.

4이면 2를 빼어 2가 남고, 16이면 2 4 6으로 4가 남습니다.

잘 보시면 이는 n² 의 경우 n이 남는것을 알 수 있습니다.

왜 그러한가하면, 제곱수차의 수열과 쉼기간 수열은 1씩 차이나기 때문에 제곱수가 한 번 다음 수열로 넘어갈때마다 쉼기간수열마다의 차이가 1씩 더벌어집니다.

즉 n²이면 n만큼의 차이가 난다는 얘기인것이죠. n만큼차이가 나기때문에 쉼기간에서 n만큼 빼주어야합니다.

그런데 2 4 6 8 10....의 수열은 112233445566...에서 온것으로 n을 빼기 전까지는 2번째(같은 수의 쉼기간중 뒤에것) n쉼기간의 마지막에 위치합니다.

n을 빼주게 되면 1번째 n쉼기간의 마지막에 위치하게됩니다.

수열로 보여드리면

112(4가 끝에 위치)23(9가 끝에 위치)34(16이 끝에 위치)4.....

가 되네요.   

그럼 n(n-1)+1은 왜 같은 쉼기간에있고 n(n-1)에 있을까요?

n(n-1)을 전개하면 n²-n으로 n²과 n만큼 차이납니다.

n²은 n쉼기간 끝에 위치하므로 n(n-1)은 바로 앞 쉼기간에 위치하는것이고, 따라서 n(n-1)+1은 같은 쉼기간에 위치하는 최소의 수가 됩니다.

 

 

 

            

 

            

이런 경우도 모두 고려해야지 제대로 된 조건이 나오겠네요.

위에서 각 행.열에 하나씩 있지 않은 경우도 있습니다.(필요조건 아님)

그리고 아래를 보시면 충분조건도 아닙니다.

대각선에 존재하는 것은 충분조건입니다.

2번 문제 n^2개의 타일중 최소 n개 이상의 타일이 감염되야합니다.왜냐하면 n개보다 적게 되면 어떻게 하던 다 감염되지 않습니다.

그리고 당연하지만 n^2개 보다도 적어야 합니다.즉 n^2>(감염된 수)>n입니다.

 

오류 있으면 댓글로 알려주세요!

 

 

비밀 댓글이 등록 되었습니다.