2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/이산수학문제풀이 43

교란순열

교란순열이란 교란순열(derangement)은 원래 위치에 있지 않은 원소만으로 구성된 순열을 말합니다. 예를 들어, 4개의 원소가 있는 경우 교란순열의 수는 9개입니다. 이를 수학적으로 표현하면, ( D_4 = 9 )입니다. 일반적으로 교란순열의 수를 나타내는 기호는 ( D_n )이며, 간단한 예로 ( D_1 = 0 ), ( D_2 = 1 ), ( D_3 = 2 ) 등으로 계산할 수 있습니다. 교란순열은 조합론에서 중요한 개념으로, 모든 원소가 원래의 위치에 있지 않도록 배열하는 경우의 수를 구하는 문제입니다. 이러한 문제는 ‘모자 문제’ 또는 '모자 확인 문제’라고도 불리며, 고전적인 확률 문제로도 잘 알려져 있습니다. 교란순열의 수를 구하는 방법에는 여러 가지가 있는데, 대표적인 방법으로는 점화식을..

[사고력수학]수열에서 2의 배수와 3의 배수를 제거하기

1부터 시작하는 자연수에서 다음과 같이 2의 배수와 3의 배수를 지우기로 했다. 다음과 같은 방법으로 지우고 남은 수 중에서 200번째 수는 무엇인지 구하고 풀이 과정을 생각해 보자. 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16... 문제풀이) 이 문제는 수열의 규칙을 찾는 문제이다. 규칙을 생각해 보면 다음과 같은 것을 발견할 수 있다. 2와 3의 배수를 제거하여 남은 수를 확인해 보면 다음과 같다. 1,5,7,11,13,17,19 위의 규칙을 자세히 살펴 보면 다음과 같은 규칙을 찾을 수 있다. 1번째 수(2*0+1) 은 (6*0+1)의 1 2번째 수(2*1)은 (6*1-1)의 5 3(2*1+1)번째 수는 7(6*1+1) 4(2*2)번째 수는 11(6*2-1) 5(2*2+1)..

[검단코딩-정보올림피아드2023초등부]3. 거짓말(5점)

네 명의 학생 A,B,C,D가 선생님 집 근처에서 축구를 하다가 한 명이 창문을 깨뜨렸다. 선생님은 누가 창문을 깼는지 알고 싶어 한다. 네 명의 학생 중 세명은 항상 진실을 말하지만 한 명은 거짓말을 할 수도 있다. 학생들은 다음과 같이 말했다. A : 저는 창문을 안 깼어요. B: A 또는 D가 창문을 깼어요. C: D가 창문을 깼어요 D: C는 거짓말을 하고 있어요. 창문을 깬 사람은 누구일까? 정답) D 문제풀이) 이 문제는 가정하기 문제이다. A가 거짓말을 했다면 나머지는 모두 진실을 얘기 할 것이다. 그렇다면 A가 창문을 깬 것이 되는데 이때 C가 거짓말을 하는 것이므로 거짓말을 하는 사람이 2명이 되기 때문에 성립하지 않는다. B가 거짓말을 했다면 역시나 A나 D가 창문을 깨면 안되는데 이 ..

[검단코딩-정보올림피아드2023초등부]2.양팔저울(5점)

양팔 저울과 각각 무게가 2kg,5kg,8kg인 추 3개와 빈 물통이 있다. 빈 물통의 무게는 0kg이며 물을 담을 수 있는 용량 제한은 없다. 양팔 저울을 한번만 이용하여 15kg 이하의 각 정수 무게에 해당하는 물을 물통에 담으려고 한다. 담을 수 없는 무게는 무엇인가?(각 무게에 해당하는 추는 1개 밖에 없고 추를 양팔 저울의 어느 쪽에도 놓을 수 있다는 것에 유의하라) 정답) 4kg,9kg,12kg,14kg 문제풀이) 양팔 저울을 어느 쪽에도 놓을 수 있다면 추의 차이만큼도 가능하다. 이것은 동적 알고리즘으로 해결이 가능한데 다음과 같은 원리이다. 0KG은 무조건 담을 수 있다. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 여기서 2kg 추가 주어진다면 2kg 과 |-2..

[검단코딩-정보올림피아드2023초등부]1. 자율주행(5점)

9차선 도로가 있고 9대의 자율주행 자동차가 왼쪽부터 차례로 한 차선에 한 대씩 달리고 있다. 각각의 자동차의 처음 속도는 차선 순서대로 아래와 같다.(단위생략) 18,15,18,13,12,13,6,15,1 각각의 자동차는 자신의 바로 왼쪽 자동차의 속도를 감지해서 만약 자신이 더 빠른 속도로 달리고 있다면 바로 왼쪽 자동차와 같은 속도가 되도록 속도를 낮춘다. 모든 자동차가 이 규칙대로 속도를 맞추었다면 최종적으로 자동차들의 속도는 모두 몇가지인가? 정답) 6가지 문제풀이) 18,15,18,13,12,13,6,15,1 위의 속도에서 왼쪽 자동차가 더 늦다면 왼쪽 자동차 속도에 맞추기 때문에 속도는 다음과 같이 된다. 18,15,15,13,12,12,6,6,1 따라서 총 속도는 18,15,13,12,6,..

[검단코딩-사고력 수학] 구슬 꺼내기

상자 안에 모양과 크기가 같은 구슬 52개가 들어 있다. 이 상자의 구슬의 색상은 다음과 같다. 빨간색 15개,주황색 14개,노랑색 10개,초록색 7개,파란색 3개,남색 2개,보라색 1개 상자는 불투명하여 안이 보이지 않는다. 여기서 무작위로 공을 하나씩 꺼낸다. 이때 같은 색 구슬을 10개 이상 꺼내려면 적어도 몇 개의 구슬을 꺼내야 하는지 구하고 풀이 과정을 생각해 보자. 더보기 정답 : 41 풀이) 빨간색 9개 주황색 9개 노랑색 9개 초록색 7개 파란색 3개 남색 2개 보라색 1개 즉 40개의 구슬을 꺼내는 동안은 같은색 10개가 나오지 않는다. 다음으로 빨간색 6개,주황색 5개,노랑색 1개가 남아 있는데 그 중 하나만 뽑아도 세개의 색상 중 하나는 같은 색 10개가 된다.

[검단신도시 코딩 사고력수학]영양제 먹는 방법 구하기

원당이는 약국에 가서 영양제를 한 통 사왔는데 영양제가 12알이 들어 있다. 용법,용량을 살펴 보니 1일 1~2알 씩 먹으라고 적혀 있다. 원당이는 하루에 한알 또는 2알을 먹을 수 있는데 원당이가 15개의 영양제를 먹는 방법은 모두 몇가지 인지 궁금해졌다. 12개의 영양제를 모두 먹는 방법은 몇가지인지 구하고 풀이 과정을 생각해 보자. 문제풀이) 원당이가 영양제 1개를 먹는 방법의 수는 하루에 1개를 먹는 1가지이다. 영양제 2개를 먹는 방법의 수는 1개씩 2일을 먹거나 하루에 2개를 먹는 2가지이다. 영양제 3개를 먹는 방법은 영양제 2개를 먹는 경우에 1개를 먹는 경우 2가지와 영양제 1개를 먹는 1가지에 2개를 먹는 방법이 있다. 영양제 4개를 먹는 방법은 영양제 3개를 먹는 3가지에서1개씩 먹는..

[사고력수학] 규칙성을 찾아 알맞은 수 써넣기

자연수 속에서 어떤 규칙을 찾아 보자. 예제 문제) 다음과 같은 수 중에서 ( ) 에 들어가야 할 자연수는 무엇인지 규칙을 찾아 보자. 1) 1, 3, 5 ,7,( ), 11 정답) 2씩 증가되는 규칙으로 9 가 들어간다. 2) 1,2,4,7,( ),16 정답) 1,2,3,4,5… 와 같은 규칙으로 증가 한다. 따라서 11 3) 1,2,4,8,( ),32 정답) *2 씩 증가되는 규칙이다. 따라서 16 문제) 1) 3,7,11,( ),19 더보기 4씩 증가되는 등차 수열이다. 따라서 정답은 15 2) 1,2,4,8,16,( ) 더보기 1,2,4,8 이 증가 된다. 즉 2의 배수 만큼 증가 된다 다음으로 증가될 값은 16이다. 따라서 정답은 16 + 16 = 32 3) 1,4,9,16,25,( ) 더보기 ..

[사고력 수학]등차수열의 원리를 이용한 삼각형 개수 세기

등차수열의 원리를 이용한 도형 개수 세기 수학 문제에서 도형의 개수를 세는 유형의 문제가 자주 출제 되는데 도형의 개수를 세는 문제도 규칙성이 있다. 이러한 규칙성을 찾아 내여 문제 풀이에 적용한다면 계산이 훨씬 간단해 질 수 있다. 1) 삼각형의 개수 세기 위의 도형에서 삼각형의 개수가 몇 개인지 세어 보자. 먼저 삼각형 1개 포함한 삼각형은 5, 2개 포함한 삼각형은 4, 3개 포함한 삼각형은 3,4개 포함한 삼각형은 2, 5개 포함한 삼각형은 1 이므로 1+2+3+4+5=15 이다. 여기서 삼각형의 개수를 셀 때 다음과 같은 규칙성을 가진 수열을 만나게 된다. 5->4->3->2->1 즉 초항은 5이고 공차는 -1 인 등차수열이다. 이 때 삼각형의 개수를 셀 때 아래의 선에서 선분의 개수를 세는 것..