WMCT Advanced Team 2016 problem 중복조합과 문제의 조건

 

 

How many positive integer solutions are there for x + y + z = 2014

such that x < y < z ?

 

x < y < z 인 조건하에, x + y + z = 2014 인 양의 정수 해는 몇개 인가 ?

 

sol)

positive integer 양의 정수 는 0 이나 음의 정수를 제외한 자연수 이다.

즉, x , y , z 가 영 이 되는 경우를 제외 해야 된다.

최소한 x , y , z 가 모두 1 이상이다.

 

2014 에서 x , y , z 에 1 개씩 모두 3개를 우선

배정하면 x + y + z = 2011 이 된다.

아무 조건도 없다면 중복조합 (2013 C 2) = 2013*2012 / 2 = 2025078 이다.

 

x < y < z 인 조건 이므로 x = y = z 는 안된다.

2014 는 3 으로 나누어지지 않기에 x = y = z 는 불가능하다.

만약 x = y 라면, 1006 개의 해가 존재한다.(ie. x = 1,2...1006)

(1,1,2012) ~ (1006,1006,2)

 

마찬가지로 , y = z 라면, 1006 개의 해가 존재한다.(ie. y = 1,2...1006)

x = z 라면,

마찬가지로 1006 개의 해가 존재한다.

x ,y ,z 가 서로 다른 해의 개수는 결국 2025078 – 3 * 1006 = 2022060 이다.

 

x < y < z 인 경우는 3! = 6 가지 중 1 가지이므로

x < y < z 인 x + y + z = 2014 인 경우는 2022060 / 6 = 337010 이다.

 

궁금하거나 모르는 부분이 있으면 연락 주세요.

010-3549-5206