[일반] 수잘갤 퀴즈

[□(112.170)]

S를 {1,...,100}의 크기가 10인 subset이라 하자.

S의 어떤 nonempty disjoint subset A,B가 존재해 A의 원소의 합과 B의 원소의 합이 같음을 보여라.

힌트 : 100은 10^2여서 쓴 게 아니다

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[□(112.170)]

왜?

[□(112.170)]

저거 optimal한거 아니어서 그럴 수는 있음

[익명(58.234)]

우선 S의 모든 subset의 갯수는 1024개, 이들이 가질 수 있는 합은 0~대략 1000보다 작은 수 사이이므로 비둘기집에 의해 무조건 S의 어떤 서로 다른 두 subset 은 같은 합을 가짐. 이제 이 두 subset 이 disjoint할 경우 => 그냥 그대로 끝, nontrivially intersect할 경우 => intersection 을 양쪽에서 다 제외시킨다. 원소가 전부 양수이기 때문에 절대 두 subset 중 하나가 다른 하나를 포함할 수가 없으므로 결과적으로 nonempty disjoint subsets 을 얻는다. 합은 당연히 양쪽에서 같은 양만큼 제외시켰으니 여전히 같음.

[□(112.170)]

오 내가 생각했던 거랑 같다

[□(112.170)]

정답입니다

[ee(220.127)]

이런문제.넘나 좋다. 자주올려줘. 이런문제 어디서 구함?

[□(112.170)]

자작임

[기괴공학도(mecheng98)]

재밌는 문제여서 추천함 ㅇㅅㅇ - dc App