당신이 다른 9명의 사람들과 함께 파티에 있는데 모두가 정확히 한 번씩 다른 사람들과 악수를 한다고 가정해 보겠습니다. 악수는 몇 번이나 이루어지나요?

이것은 "악수 문제"이며 제가 가장 좋아하는 문제 중 하나입니다. 수학 교사로서 저는 해결책에 도달할 수 있는 방법이 매우 다양하고 이러한 전략의 다양성과 상호 연결성이 수학에서 창의적 사고의 힘을 아름답게 보여주기 때문에 그것을 좋아합니다.

한 가지 해결책은 다음과 같습니다. 각 사람이 다른 사람과 악수하는 것으로 시작합니다. 9명이 각각 10번의 악수를 하면 총 90×90=2번의 악수를 합니다. 그러나 이는 모든 악수를 두 번(각 셰이커의 관점에서 한 번) 계산하므로 실제 악수 횟수는 $latex frac{45}{XNUMX} = XNUMX$입니다. 승리를 위한 간단하고 사랑스러운 계산 논쟁!

문제를 해결하는 완전히 다른 방법도 있습니다. 손님이 한 번에 한 명씩 도착하고 거기에 도착하면 참석한 모든 사람과 악수를 한다고 상상해 보십시오. 첫 번째 사람은 악수할 악수가 없으므로 0인 파티에서는 전체 악수 횟수가 1입니다. 이제 두 번째 사람이 도착하여 첫 번째 사람과 악수를 합니다. 이렇게 하면 전체 악수에 한 번의 악수가 추가되므로 1인 파티에서는 총 악수가 XNUMX + XNUMX = XNUMX이 됩니다. 세 번째 사람이 도착하여 처음 두 명의 손님과 악수를 하면 총 악수 횟수에 두 번의 악수가 추가됩니다. 네 번째 사람이 도착하면 총 악수 횟수에 세 번의 악수가 추가됩니다.

이 전략은 일련의 핸드셰이크를 재귀적으로 모델링합니다. 즉, 시퀀스의 각 용어는 그 앞에 오는 용어와 관련하여 정의됩니다. 아마도 가장 유명한 재귀 수열인 피보나치 수열에 대해 잘 알고 계실 것입니다. 1, 1, 2, 3, 5, 8, 13, 21로 시작하여 이전 두 항의 합과 동일한 각 후속 항으로 계속됩니다.

아래에서 볼 수 있듯이 재귀는 광범위한 수학적 아이디어를 생각하기 위한 유연하고 강력한 프레임워크입니다. 그리고 헤마찬드라(Hemachandra)와 같은 고대 인도 학자들이 1150년까지 이러한 종류의 수열에 대해 알고 있다고 인정을 받았음에도 불구하고 그들은 오늘날의 수학자들에게 여전히 흥미로운 과제를 제시하고 있습니다.

재귀적 사고가 악수 문제를 해결하는 데 어떻게 도움이 되는지 살펴보겠습니다. $latex a_n$을 한 번의 악수 횟수와 동일하게 두면 n-person party의 경우 다음 공식으로 이 재귀 관계를 나타낼 수 있습니다.

$라텍스 a_n = a_{n-1} + n–1$

이는 한 번의 악수 횟수를 알려줍니다. n-개인 파티($latex a_n$)는 ($latex a_n$)에서 악수한 횟수와 같습니다.n − 1) 1인 파티($latex a_{n-XNUMX}$) 플러스 n − 악수 1회 더, 새로운 사람이 도착하면 이미 발생한 악수에 일정 횟수의 새로운 악수를 추가한다는 아이디어를 포착합니다.

악수 문제의 특정 버전에서 우리는 10명이 참여한 파티에서 악수한 횟수인 $latex a_{10}$를 알고 싶습니다. 이를 통해 재귀 관계를 사용한다는 것을 알아낼 수 있습니다.

$라텍스 a_{10} = a_9 + 9$

$latex a_{10}$의 값을 찾으려면 $latex a_9$의 값을 알고 여기에 9를 더하면 됩니다. $latex a_9$의 가치는 어떻게 알 수 있나요? 물론 재귀를 사용하여!

$라텍스 a_9 = a_8 + 8$

이제 $latex a_8$의 값을 찾으려면 $latex a_7$ 등을 알아야 하는 $latex a_6$의 값을 찾아야 합니다. 이 시점에서 이것이 일종의 무한 하강으로 영원히 계속될 것이라고 걱정할 수도 있지만, 일단 $latex a_1$에 도달하면 우리는 끝난 것입니다. 왜냐하면 우리는 XNUMX인 파티에서 총 악수 횟수가 XNUMX이라는 것을 알기 때문입니다.

$라텍스 a_1 = 0$

이 초기 또는 "시드" 값은 재귀 시퀀스의 주요 기능입니다. 재귀 관계를 사용하여 시퀀스를 통해 역추적하는 프로세스가 종료되도록 보장합니다. 시드 값에 도달하면 역추적이 중지되고 목록을 통해 앞으로 작업하여 원하는 값을 얻을 수 있습니다.

$라텍스 a_1 = 0$

$라텍스 a_2 = a_1 + 1 = 0 + 1 = 1$

$라텍스 a_3 = a_2 + 2 = 1 + 2 = 3$

$라텍스 a_4 = a_3 + 3 = 3 + 3 = 6$

$라텍스 CDOT$

$라텍스 a_{10} = a_9 + 9 = 36 + 9 = 45$

목록을 살펴보면 45명이 참여한 파티에서 총 10번의 악수가 있음을 알 수 있으며 이는 초기 계산과 일치합니다. 여러분이 제 학생들과 같다면, 우리가 이미 답을 알고 있는데 왜 이 문제를 해결하기 위해 다른 방법이 필요한지 물을 것입니다. 특히 이 두 번째 접근 방식은 더 오래 걸리는 것 같기 때문입니다.

좋은 질문입니다. 한 가지 대답은 재귀적 접근 방식이 이 문제에서 무슨 일이 일어나고 있는지에 대해 완전히 다른 관점을 제공한다는 것입니다. 그리고 다른 관점은 모든 일에서 그렇듯이 수학에서도 유용합니다. 개념을 이해할 수 있는 다양한 기회를 제공하고, 막혔을 때 도움이 될 수 있는 다양한 도구를 사용할 수 있도록 해줍니다.

특히 재귀는 수학의 모든 곳에 있기 때문에 유용합니다. 예를 들어, 수학 시간에 모든 사람이 배우는 선형 관계, 즉 일정한 변화율이 특징이고 평면의 선으로 표시되는 선형 관계에서 발생합니다. $latex f(x) = 3x + 5$와 같은 선형 함수는 재귀 공식으로 생각할 수 있습니다.

$라텍스 a_0 = 5$

$라텍스 a_n = a_{n-1} + 3$

$latex f(2)$에 대해 생각하는 더 확실한 방법은 $latex f(2) = 3 곱하기 2 + 5 = 11$일 수도 있지만, 또 다른 방법은 $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. 선형 함수의 기본 특성인 일정한 변화율을 재귀적으로 모델링하면 이 관계에 대해 생각할 수 있는 또 다른 방법이 제공됩니다. 일정한 곱셈 변화를 특징으로 하는 지수 함수에서도 동일한 작업을 수행할 수 있습니다.

재귀적 사고는 일련의 숫자를 넘어서도 작동합니다. 연립방정식을 풀어본 적이 있다면 아마도 재귀적 접근 방식을 적용했을 것입니다. 시스템을 해결하려면

$라텍스 2x + y = 10$

$라텍스 3x – y = 5$

먼저 두 방정식을 함께 추가하여 다음을 제거할 수 있습니다. y 결과는 $latex 5x = 15$라는 방정식이 됩니다. 이 문제를 해결하여 $latex x =$ 3을 얻고, $latex y = 4$를 찾는 것으로 대체하면 완료됩니다. 이 접근 방식은 시스템에 대한 솔루션이 솔루션에서 더 작은 관련 시스템으로 구축되는 재귀 알고리즘을 활용합니다. 예를 들어, 3×3 시스템을 풀려면 변수 하나를 제거하여 2×2 시스템으로 바꾸고 다시 1×1 시스템으로 바꾸면 됩니다. 이 해결하기 쉬운 단일 방정식은 이 재귀 프로세스의 시드 값과 같습니다. 이는 역추적의 끝을 알리고 거기에서 재귀 시퀀스처럼 방정식 체인을 백업하는 방식으로 작업합니다.

재귀적 증명 기법도 있습니다. 예를 들어, 기하학의 유명한 공식은 다각형 각도 합 공식입니다. 이는 다각형의 내각 측정값의 합을 말합니다. n면 다각형은 $latex (n-2) 곱하기 180^{circ}$입니다. 이 결과를 증명하는 한 가지 방법은 다음과 같이 시작하는 것입니다. n-삼각형을 제거하면 어떤 일이 일어날지 상상해 보세요.

삼각형을 제거하면 n-에 (n − 1)-gon, 180도 내부 각도 측정도 제거합니다. 이것은 재귀 관계입니다. n-gon은 (에 대한 내각 합보다 180도 더 큽니다.n - 1)-곤. 일반적인 결과를 얻으려면 시드 값에 도달할 때까지 삼각형을 계속 제거하십시오. 이 상황에서는 세 개를 제외한 모든 삼각형을 제거했을 때 발생합니다. n-곤의 정점. 이 시점에서 초기 다각형은 내부 각도 합이 180도인 것으로 알려진 삼각형으로 축소되었습니다. 이제 다시 돌아가 각 단계에서 180도를 더하면 공식을 얻을 수 있습니다.

우리 이야기로 돌아가서, 악수 문제 자체는 우리가 창의적으로 생각하고 문제에 대한 다양한 관점을 함께 연결할 때 무엇이 ​​가능한지 보여줍니다. 일련의 악수에 대한 재귀 모델을 가지고 놀면 다음과 같습니다.

$라텍스 a_1 = 0$

$라텍스 a_n = a_{n-1} + n – 1$

좋은 패턴이 나타납니다.

$라텍스 a_2 = a_1 + 1 = 0 + 1$

$라텍스 a_3 = a_2 + 2 = 0 + 1 + 2$

$라텍스 a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$라텍스 CDOT$

$라텍스 a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

이제 우리는 문제에 대해 생각하는 새롭고 일반적인 방법을 갖게 되었습니다. n-개인 파티는 첫 번째 파티의 합계와 같습니다. n − 1개의 양의 정수.

우리의 원래 접근 방식을 다시 생각해 보세요. 에 n-개인 파티, 각 사람이 다른 사람과 악수합니다. n – 1명. $latex n (n-1)$ 제품은 모든 악수를 두 번 계산하므로 총 악수 횟수는 $latex frac{n(n-1)}{2}$입니다. 그러나 우리의 다양한 방법은 동일한 것으로 간주되므로 동일한 결과를 산출해야 합니다. 특히 이는 다음을 의미합니다.

$라텍스 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

악수 문제에 대한 다양한 접근 방식을 연결함으로써 우리는 첫 번째 합에 대한 닫힌 공식을 얻습니다. n − 1개의 양의 정수. 하지만 우리는 더 많은 것을 얻습니다. $latex frac{n(n-1)}{2}$라는 표현은 분수를 포함하지만 정수의 합과 같기 때문에 정수여야 합니다. 이것은 정수론의 간단한 사실을 증명합니다: 모든 정수에 대해 n, $latex frac{n(n-1)}{2}$는 정수입니다.

이와 같은 종류의 주장은 현대 수학에도 계속해서 힘을 실어주고 있습니다. 일례로 2000년대 초반 연구자들은 놀라운 결과를 보여줬습니다 Somos 시퀀스로 알려진 재귀 시퀀스에 대해 너무 중요하다는 것을 보여줍니다. 창의적인 연결의 힘을 통해 수학자들은 자신이 있었던 곳을 이해함으로써 어디로 갈 수 있는지 다시 한 번 발견했습니다.

운동

1. 다음과 같이 재귀적으로 정의된 수열에 대한 닫힌 공식을 찾으세요.
$라텍스 a_1 = 1$
$라텍스 a_n = a_{n-1} + 2n – 1$

2. 열 끝에서 $latex frac{n(n-1)}{2}$ 표현식은 분수가 포함되어 있음에도 불구하고 $latex frac{n(n-1)이므로 정수로 표시되었습니다. )}{2}$는 무언가를 세어본 결과입니다. 이 표현식이 정수여야 함을 보여주는 정수 이론 인수도 있습니다. 그것은 무엇입니까?

3. 재귀 수열의 처음 몇 항을 찾으세요.
$라텍스 a_1 = 1$
$latex a_n = 분수{1}{1+a_{n-1}}$

4. 재귀 수열의 처음 몇 항을 찾으세요.
$라텍스 a_1 = 1$
$라텍스 a_2 = 1$
$라텍스 a_n = a_{n-1} – a_{n-2}$