푸는 맛이 쏠쏠하니까 고민해보는것도 괜찮음. 근데 쉬울 듯



문제1)

1부터 100까지의 자연수 중 50개의 숫자에 마이너스(-) 기호를 붙인다.

새로 만들어진 100개의 숫자의 합은 항상 짝수임을 증명하라.

예) -1-2-3-4-5-...-50+51+52+53+54+55+...+100=49X50이므로 짝수이다.




풀이1)

새로 만들어진 수에서 음수를 모은 집합을 A, 양수를 모은 집합을 B라고 하자. A에 속한 어떤 숫자를 a, B에 속한 어떤 숫자를 b(당연히 b는 음수이다.)라고 하자. a,b의 부호를 바꾸면 수의 구성은 달라져도 음수의 개수와 양수의 개수는 여전히 각각 50개이다.

그런데 부호를 바꾸기전에는 100개의 숫자의 합에 a+b가 있었지만 부호를 바꾸고 나서 다시 100개를 더하게 되면 –a-b가 된다. 두 수의 부호를 바꾸기 전과 후의 차이는 정확히 –2a-2b만큼 차이가 난다. 즉 두 개씩 부호를 바꾸게 되면 짝수만큼의 변동이 일어나게 된다.

-1-2-3-4-5-...-50+51+52+53+54+55+...+100=49X50는 짝수이고, 여기서 숫자 두 개를 원하는 만큼 반복해서 부호를 바꾸어도 여전히 50개의 숫자에 (-)를 붙인 것과 똑같이 된다. 양수와 음수를 하나 골라서 부호를 바꿀때마다 짝수만큼 차이가 나므로 몇 번을 바꾸든 짝수가 된다.(짝수에서 짝수를 더하든 빼든 짝수가 나온다.)




문제2)

50개의 숫자에 마이너스를 붙인뒤 모두 합해서 나올 수 있는 값의 최댓값을 M, 최솟값을 m이라고 하자. 1부터 100까지의 자연수에서 50개의 숫자에 (-)부호를 적당히 붙여서 M와 m사이에 있는 모든 짝수를 만들어 낼 수 있다. 이를 증명하라.

예) 0은 명백히 최댓값과 최솟값 사이이며 실제로 –1+2+3-4+5-6-7+8+...-97+98+99-100=0이므로 더했을때 0이 나오도록 양수와 음수를 정할 수 있다.




풀이2)

M보다 작은 어떤 수를 k라고 하자. 합이 k가 되는 50개의 음수와 50개의 양수에서 -2+1처럼 합이 –1이 되는 숫자 두 개가 있다면 부호를 바꾸고 나서 더하게 되면 k+2가 된다. (예를 들어 –2+1의 부호를 바꾸면 +2-1이 되므로 특정 부분의 합이 –1에서 1로 바뀌므로 기존보다 2씩 커진다.)

이제 숫자 100개의 합이 M보다 작은 50개의 음수와 양수 중에서 두 수의 합이 –1이 되는 두 수가 항상 존재함을 증명하자. 양수 중에서 가장 작은 수를 s라 두자. 그러면 음수에 -s-1이 있다면 합이 –1이므로 충분하다. 만약 그렇지 않다면 양수에 s+1이 있다.(그 이유는 면 –s-1나 s+1중에 하나는 있어야하기 때문이다.) 이제 음수에 –s-2이 있으면 충분하게 된다. 만약 그렇지 않다면 마찬가지로 양수에 s+2가 있게 된다. 음수에 -s-k가 존재하지 않아 충분한 숫자가 계속 커져서 양수에 100이 있게 되는 상황이 온다면 s는 51이 된다. 왜냐하면 양수에 s, s+1, s+2, s+3, ..., 100이 있기 때문이다.(s는 가장 작은 양수이다.) 그 합은 최댓값인 M이며 합이 M보다 작다는 가정에 모순이므로 s+k, -s-k-1인 양수와 음수가 존재해야만 한다.

그러면 m부터 적당한 두 수의 부호를 바꿔가며 2씩 더하게 되면 m과 M사이의 모든 짝수를 만들어 낼 수 있게 된다.