[이산수학] Mathematical Thinking in computer Science 1주차

증명(proof)

수학자에게 증명이란 기본 도구이지만 프로그래머에겐 더 의심 많은 것이다.

증명이란 다른 사람들에게 것을 사용하기 위한 준비가 되었음을 확신하게 하는 논쟁이다.

어떻게 증명을 이해하고 발견하고 설명하고 즐길지 공부할 예정이다.

 

문제) 88체스판을 12 타일로 채우기 (비는 칸과 겹치는 칸 없도록)

→ 타일채우기가 불가한 경우를 증명해보자

코너 1칸만 잘릴 경우 항상 1칸이 남는다. 8*8-1=63 (홀수) → 불가능함을 증명할 수 있음

서로 대각선에 있는 코너 2칸이 잘린 경우 2칸이 남는 경우가 생긴다.

→ 체스보드의 같은 색이 사라질 경우에는 타일 채우기가 불가능함.(1*2 타일에서 검정, 흰색이 하나의 짝이 되므로)

 

정리 → 대각선 두 코너가 없는 88 체스보드는 12 도미노로 채워질 수 없다.

이와 같은 예제를 통해 증명은 확신을 줄 수 있음을 알 수 있다.

만약, 대각선 코너가 아니라면 타일을 다 채울 수 있을까?

만약, 다른 색의 두 타일이 없다면 타일을 다 채울 수 있을까?

 

존재 증명법 (Existence Proofs)

증명은 주어진 속성이 존재하는지에 달려 있다.

증명이란 하나의 예시이다.

 

문제) 합동(같은 모양과 크기)인 조각으로 자르기

Tensegrity(장력tension+무결성integrity) : 털실로 연결된 스틱(또는 빨대)으로 서로 닿지 않으면서 고정되어야 함

 

문제) 가장 앞 자리 수를 지웠을 때 7배 작아지는 두 자리 수는?

문제) split 똑같이 나누기 → 두 가방에 똑같이 나누어 담는다고 생각하고 문제 풀기, 숫자를 다 더해서 짝수여야 함

 

<오늘의 정리>

claim (증명되지 않은) 주장

예시 하나만 있어도 증명할 수 있음

 

coursera Introduction to Discrete Mathematics for Computer Science 과정 중 Mathematical Thinking in coumputer Science 1주차 내용 정리