[일반] 이산수학 1문제만 도와주십셔...

[익명(14.39)]

Matousek 교재 추천받아서 이산 독학하고 있습니다.

그런데 이 책이 솔루션도 없고, 책 뒤에 힌트도 부실해서 문제 풀기가 힘듭니다...

저 문제에서 몇시간째 헤메고 있는데 도와주실 수 있나요?

특히 저 n^1/4가 어쩌다 나온 것인지 궁금합니다.

문제가 실린 파트는 Partial ordering입니다.

- dc official App

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

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

[익명(14.39)]

조금만 더 자세히 설명해주실 수 있나요ㅠㅠ - dc App

[익명(2.222)]

n^{1/2} 이상의 자연수 t와 index j_1 < j_2 < ... < j_t가 존재해서 a(j_1) , ... , a(j_t)는 increasing이거나 decreasing임. 이제 부분수열 b(j_1) , ... , b(j_t)를 고려하자. 그렇다면 다시 적어도 t^{1/2}이상의 자연수 k와 index u_1 < u_2 < ... < u_k가 존재해서 b(j_{u_1}) , ... , b(j_{u_k})는 increasing이거나 decreasing임. 한편 a(j_{u_1}) , ... , a(j_{u_k})는 monotone한 부분수열 a(j_1),...,a(j_t)의 부분수열이니 마찬가지로 increasing이거나 decreasing임.