조합[심화문제2] 5-2

출처:디모데성경연구원

#5.28팀이 참가하는 축구대회가 열렸다. 각 팀은 다른 팀과 꼭 한 번씩 경기하였고, 매 경기마다 이기면 승점 2, 비기면 1, 지면 0점씩을 받는다. 75%를 넘는 경기가 무승부였다. 그럼 같은 승점의 두 팀이 존재함을 보여라.

이김=2 비김=1 짐=0->이김=1 비김=0 짐=-1 로 바꾼다.

귀류법:임의 두 팀은 승점이 다르다.

(승패가 정해진 경기수)<1/4×28C2=94.5

k번 팀의 총 승점=Xk

if)

Xk>0: k번 팀은 적어도 Xk번을 이겼다.

Xk<0: k번 팀은 적어도 Xk번을 졌다.

S=(각 팀의 승패가 갈린 경기수의 총합)≥|x1|+|x2|+...+|x28|=0+1+...+13+1+2+...+14=196

(승패가 정해진 경기수)≥1/2×S=98

모순

 

#6.12명에서 두 명을 선택하고 나머지 10명에서 다섯 명을 더 선택하여 다섯 명 각각이 다음을 만족하도록 할 수 있음을 증명하시오.

처음에 선택한 두 사람과 친구이거나 아니면 이 두 명과 친구가 없다.

임의 두 점 x,y:f(x,y)=x,y와 모두 이웃+모두 안 이웃 점 개수 f(x,y)≤4

N=안 이웃 선 2개로 구성된 V자와 이웃 선 2개로 구성된 V자 개수≤12C2×4=264

한점 기준에서 보면 N≥12(5C2+6C2)=300

모순

 

#7.11×11 표의 몇 개의 칸에는 + 가 하나씩 있고 이 표에 있는 + 의 개수는 짝수이다. 또한 임의의 2×2 격자 정사각형에 포함된 + 의 개수는 짝수이다. 이 때, 이 표의 주대각선 위에 있는 11개의 칸에 있는 + 의 개수는 짝수임을 증명하시오.

※문제풀이를 시작하기 전에 앞서 사진의 주인이신 권○○님께 감사를 표합니다.

+의 총 개수는 짝수개이고 임의의 2×2 정사각형 안의 +개수도 짝수개이다.

A의 내부 + 개수=a

B의 내부 + 개수=b

a,b≡0(mod 2)

a+b≡S₁+S₂+2D≡S₁+S₂≡0(mod 2)

주대각선 + 개수≡전체 + 개수-(S₁+S₂)≡0(mod 2)

(단, S₁과 S₂는 각각 A-B와 B-A이다.)

 

#8.n×n 체스판의 한 대각선의 칸을 1로 채우고 나머지 칸을 모두 0으로 채웠다. 스스로 교차하지 않는 임의의 닫힌 '루크-회로'(체스판의 모서리에 평행한 선분들로 이루어진 닫힌 경로) 의 모든 칸의 수들을 1씩 증가시킬 수 있다. 이러한 시행으로 모든 칸의 수가 똑같아지도록 할 수 있는가?

※문제풀이를 시작하기 전에 앞서 사진의 주인이신 권○○님께 감사를 표합니다.

2|n일때

체스판 컬러링

조합[체스판] 1-1

'루크-회로' R이 지나는 흰 칸과 검은 칸의 개수가 같다.

시행전: S=흰칸 숫자합-검은칸 숫자합=일정

맨 마지막에 모든 칸의 숫자가 같아지려면 S=0 모순

 

2∤n

귀납가정:n보다 작은 홀수 m, m×m은 모든 수를 같게 할 수 있다.(m=3일때 성립)

 

사진에 나온 것처럼 C의 모든 숫자를 같게 한 뒤, A의 모든 숫자에 1을 더하고 B의 모든 숫자에도 1을 더한다.

결과적으로 C의 모든 칸의 숫자는 같고 n×n 정사각형의 테두리부분에 계속 1을 더해줘서 다른 칸의 숫자들과 같게 맞춰줄 수 있다.

따라서 n이 홀수일때만 가능하다.