20060527, 오늘의 문제 #1

[아리아빠(143.248)]

앞으로 같은 짓 여러번 할 것 같은데, 따로따로 썼다가 묻히는 것보다 이렇게 제목이라도 통일해 놓으면 좀 낫지 않을까 싶어서 정리해 볼라고. 뭔가 재밌는 문제 없을까 해서 수학갤 찾아오는 횽들을 위한 거야. 고로 악플은 반사 문제들은 불펌이야. 저작권 생각은 해 봤는데, 어차피 공개되어 있는 문제들이고 이익을 보는 것도 아닌 이상 괜찮지 않을까 싶어서. 내가 좀 지적 재산권 개념이 없기도 하고. 문제 수준은 일단 내가 풀어보고 올리는 거니까 횽들이 보기에는 많이 쉬울지도 몰라. 그건 이해해줘.

[ㄷㄷ(61.40)]

횽들이 보기에는 많이 쉬울지도 몰라. 그건 이해해줘. <-- 이부분은 농담이지? 자라나는 새싹을 밟지 말아줘 ㅎㅎ

[추얼(143.248)]

1. f_i is odd when i>=3. if f_i != f_(i+1) and both odd, then max(f_i, f_(i+1) ) > max(f_(i+2) , f_(i+3)) because f_(i+2) <= {f_i + f_(i+1)}/2 and f_(i+3) <= {f_i+3*f_(i+1)}/2

[추얼(143.248)]

so max(f_(2i+1),f_(2i+2) ) is strictly decreasing when i>=1. and trivially max(f_(2i+1),f_(2i+2) ) is always positive integer. f_i is decreasing and bounded below so, f_i should converge and integer. by Well ordering property of positive integer, f_i is eventually constant

[추얼(143.248)]

2. suppose a!=b. if d|a and d|b and d odd, then d should divide all f_i. (trivial) and suppose f_n is constant(=m) for all n >N. (by 1. there exist such N) (m is obviously odd)

[추얼(143.248)]

Claim. 'all m divide f_i' proof) suppose not. then find largest t such that m doesn't divide f_t. ( there exist such t because of 1. and hypothesis) m|f_(t+1) and m|f_(t+2) by definition of t. m|f_(t+2) | f_(t+1) + f_t by definition of sequence. and m|f_(t+1). it means m|f_t. this contradicts. so we prove claim.

[추얼(143.248)]

so, if d|a, d|b, and d odd, d divide then eventual value. and eventual value should divide all f_i by claim, so also divide a and b. so eventual value is largest odd factor of gcd(a,b)

[추얼(143.248)]

메모장에 치고 옮겨봤는데 -_- 제가 봐도 참 보기 힘드네요;; 고치긴 귀찮아서 -_-

[추얼(143.248)]

써놓고 보니 살포시 사소한 오류도 보이긴 하네요 ;; 뭐 별로 중요한건 아니니까 넘어가도 될듯;;

[&#52898;(221.140)]

어허헝,,, 영어다

[추얼(143.248)]

실수한거는 strictly decreasing 을 nonincreasing 으로 고쳐야 하고 뭐 대충 그런거;;

[까뷔(155.198)]

그냥 숫자 대입해봤더니 a=b일 경우 f_n = a = b for all n>2 이구, a 는 b가 아닐경우 f_n = f_n+1 = f_n+2 = ... = 1 for some n>2 인 것 같아.. 근데 이걸 어떻게 증명하지? 흠흠

[까뷔(155.198)]

아니닷 a는 b가 아닐경우 f_n = 1 일 필요는 없네.. 어렵당 ㅠ.ㅠ

[까뷔(155.198)]

추얼횽아.. 저 맨 위에 f_i != f_(i+1) 에서 ! 가 무슨 뜻이야? 팩토리얼이란 뜻은 아닐테고.. 처음부터 보는게 막혀서 그다음 것도 이해 못했어 ㅠ.ㅠ

[까뷔(155.198)]

그리구 맨 마지막에 the largest odd factor of gcd(a,b) 는 결국 gcd(a,b)랑 똑같은 말 아니야?

[까뷔(155.198)]

a랑 b둘다 홀수면 gcd(a,b)도 홀수 일테고.. the largest odd factor of an odd number is itself 아니야?

[추얼(211.216)]

!= 는 같지 않다. 라는 뜻. .a,b 가 홀수라는 소리 없음.

[추얼(143.248)]

아, 홀수라는 소리 있구나 -_-;; 문제 잘못읽음..;;

[까뷔(155.198)]

아 이문제 G-_-g