08. 중복 조합: 부정 방정식의 해의 개수

---

---

08. 중복 조합: 부정 방정식의 해의 개수

 

---

🧸 01. Intro

       : 안녕하세요, 삐약 은지입니다😊

         오늘은 중복 조합을 배우면 빠질 수 없는 "부정 방정식의 해의 개수"에 대해 알아보겠습니다

---

 

---

🧸 02. 부정 방정식의 해의 개수 

       : 부정 방정식이란 미지수의 개수보다 식의 개수가 적은 경우를 의미합니다 

         a + b + c  = 10과 같이요 😊

 

         부정 방정식을 만족하는 해의 개수는 무수히 많습니다 (실수)

         때문에 저희는 고교 과정에서 음이 아닌 정수를 조건으로 해를 구했었습니다

         그러면 만족하는 모든 실수 해를 구하는 것보다는 더 적기 때문입니다

 

         음이 아닌 정수를 해로 갖는 부정 방정식을 푸는 방법은 일일이 대입해서 풀 수도 있지만

         간단하게 중복 조합을 이용해서 풀 수도 있습니다

 

         예시를 하나 들어보겠습니다 

         a + b = 4를 만족하는 음이 아닌 정수를 갖는 해의 개수를 구한다고 가정해보겠습니다

         일일이 대입해서 풀 경우 해는 (0, 4), (1, 3), (2, 2), (3, 1), (4, 0)로 총 5가지 입니다

     

         하지만 이를 a와 b를 중복 선택해서 4가 나오는 경우의 수로 해석을 하게 되면

         아래와 같이 작성할 수 있습니다 

         이번에는 다른 예시를 살펴보겠습니다

         만약 2x + y + z = 5를 만족하는

         음이 아닌 정수를 갖는 해의 개수를 구한다고 가정해보겠습니다

         이때는 미지수 x, y, z 의 계수가 모두 1이 아닌 x의 계수에 2가 있으므로

         분류해서 풀어야합니다

 

         (Point 1)

               : 미지수의 계수가 모두 1일때 균등한 분배가 가능하기에

                 중복 조합을 바로 적용할 수 있습니다

         (Point 2)

               : 미지수의 계수가 다를 경우 단순한 분배가 아닌 가중치가 있는 분배 문제가 되기에,

                 분류해서 풀어야 합니다 (바로 중복 조합 적용 불가능!)

    

         x를 기준으로 푼다면 아래와 같이 분류할 수 있습니다 

           ⓐ x = 0 → y + z = 5

           ⓑ x = 1 → y + z = 3 

           ⓒ x = 2 → y + z = 1

 

          이제 미지수의 계수가 모두 1이 되었으므로,

          중복 조합을 이용하여 각각 구해주면 아래와 같습니다 😊

           ⓐ 2H5 → 6C5 = 6C1 = 6

           ⓑ 2H3 → 4C3 = 4C1 = 4

           ⓒ 2H1 → 2C1 = 2

 

          분류 결과로 저희는 6, 4, 2를 얻었습니다

          이때 분류는 마지막에 합의 법칙을 통해 하나로 합쳐주면 되므로,

          결과적으로 정답은 12가 됩니다 😄 

---

 

---

🧸 03. 부정 방정식 2가지 유형

       : 부정 방정식에는 "이상 조건" 일때와 "이하 조건"일 때로 

         총 2가지의 유형이 존재합니다

 

         "이상 조건"의 예시를 먼저 들어보겠습니다

         부정 방정식 x + y + z = 6이 있고, x, y, z가 모두 자연수일 때 

         음이 아닌 정수 해의 개수를 구하는 문제를 풀어야한다고 가정해보겠습니다 

 

         이때는 미지수들이 모두 자연수 조건이므로 각 변수는 반드시 1 이상이어야 합니다
         즉, x, y, z 각각이 최소한 1개씩은 포함되어야 합니다 🤔

         따라서 이를 고려하면,
         이미 x, y, z가 각각 1개씩 포함되었으므로
         남은 합은 6 - 3 = 3이 됩니다

 

         결국 문제는
         "x + y + z = 3의 음이 아닌 정수 해의 개수를 구하는 부정방정식”으로
         다시 해석할 수 있습니다 😯

       

         결과적으로 이렇게 재해석한 식, x + y + z = 3 의 해의 개수는
         원래의 식 x + y + z = 6에서 x, y, z가 자연수일 때 음이 아닌 정수 해의 개수가 됩니다 (아래 참고)

 

         다음으로 알아볼 내용은 "이하 조건"입니다

         이하 조건이란 각 변수의 값이 특정 수 이하일 때를 조건으로 주어진 경우를 말합니다 🧐

         예를 들어보겠습니다

         x + y + z = 5의 음이 아닌 정수 해의 개수를 구한다고 가정해보겠습니다

         단, 이때 x, y, z는 모두 3 이하일 때 입니다

 

         이하 조건을 푸는 대표적인 방법은 여사건(Complementary Case)을 이용하는 것입니다

         각 변수 x, y, z가 가질 수 있는 최댓값은 3이므로,
         세 변수가 모두 최댓값을 가질 때의 총합은 3 + 3 + 3 = 9가 됩니다

 

         따라서, x + y + z = 5라는 식은
         최대값 9에서 4만큼 부족한 경우,
         즉 x′, y′, z′가 만들어내는 여사건 부정 방정식으로 바꾸어 생각할 수 있습니다

 

         따라서 x + y + z = 5의 여사건 부정 방정식은 아래와 같이 나타낼 수 있으며,

         저희는 아래 식을 풀면 됩니다 

 

         아래 식에서 각 변수가 가질 수 있는 값의 범위를 살펴보면,
         우변이 4이므로 x′은 0부터 4까지의 값을 가질 수 있습니다 (y', z'도 동일)

         왜냐하면 x′ = 4일 때는 y′ = z′ = 0이면 식이 성립하고,
         반대로 x′ = 0일 때는 y′ + z′ = 4가 되면 되기 때문입니다 🤔

 

         그런데 여기서 x′, y′, z′는 모두 최대 3까지만 가능하므로,
         전체 경우의 수에서 (4,0,0), (0,4,0), (0,0,4)의 세 가지 경우를 제외해야 합니다

         이는 곧, 중복 조합으로 구한 전체 음이 아닌 정수 해의 개수에서
         각 변수 자리에 4가 위치할 수 있는 경우의 수인 3C1 을 제외하는 것과 같은 의미입니다

         따라서 식을 정리하면 아래와 같이 나타낼 수 있습니다

---

 

---

🧸 04. 마무리

       : 오늘은 부정 방정식과 부정 방정식의 2가지 유형인

         "이상 조건"과 "이하 조건"에 대해 살펴보았습니다 😊

 

         다음 시간에는 "이항 정리"에 대해 살펴보게습니다

         그럼 모두 안녕~👋

---