이문제보고
x^k=a mod n의 근이존재하기 위한 조건 생각해서
q=1 mod p이지만
p^(q-1/p)=1 modp가 아닌 q를 찾으면 되겟네 해서
ordp=p인 q를 찾으면 되겠고
p^p-1을 나누지만 p-1의 배수가 아닌 q는 primitive prime divisor로서 존재하니까 ordp=p가 되어서 증명됨
이런 생각의 흐름으로 풀었는데.
이게 IMO 문제라더라?
대체 고딩이 풀라고 만든 문제를 왜 이렇게 정수론을 알아야 풀수있게 만들어 놓은건가? 라는 생각이 드는거야
그래서 답을 찾아봤더니
아무런 정리도 쓰지않고 존나 깔끔하고 신박함
근본적인 아이디어야 똑같은데 정수론 공부를 안하고도 저런풀이를 떠올린다는게 가능함?
혹은 당연히 했을거라고 생각하고 낸문제임?
원래 저런 직관성, 창의성을보는거임
저런걸 공부안하고도 떠올린다는게 놀라운데 나는 공부하고도 못하겟는데 진짜 깊게 이해하진 못했다는건가
고등학교 수학 제일 잘하는 애들 선발하는거니까 세계에서 뭐
이러면 어떻고 저러면 어떠리, 풀기만 하면 되는 것을.
시험 보는 애들이야 다 정수론을 공부하긴 하지만, 올림피아드의 본 목적은 누가 그런 교육 안 받고도 이런 문제 풀 수 있나 발굴하자는 것에 가깝긴 함
그리고 문제 출전 좀 명확히 밝혀주셈 imo 문제라면 어느 해 몇번인지
Imo shortlist 2003 정수론 problem 6라고함
shortlist면 최종 후보 문제인데 이렇게 대학 지식이 대놓고 유리한 문제는 걸러져서 안나옴 IMO 나올 정도면 대학 과목 웬만한건 배우고 와서 ~안하고 가능함? 이건 별로 의미 없음
안하고 풀수 있는게 진짜 실력 아니냐
Shortlist라서 이런문제가 있다 정도로 정리할수있겠네
솔직히 background없이 푸는걸 불가능하다고 말하긴 어려운데 Background 없이 제한시간안에 푸는건 불가능하다고 봄
좀 신기하기는 하네 ㅇㅇ 근데 한국도 수능에 억지로 꼬는 문제 안내고 배운 하에서 머리쓰는 문제 낼수 있음. 안그러고 이상하고 괴랄한 문제 내는게 문제지
수능도 사실 풀수는 있지만 미적분학 지식있으면 더 쉬운 문제 가끔씩 보이긴하지 근데 최대한 지양하는 노력도 보이긴해서 훌륭하다고 느껴짐
정수론 안배우고 IMO나가는 학생이 있긴한가
가능한 사람이 IMO나가는거지
개소리임 당연히 세계 역사상 누군가는 정수론을 안배우고 저 논리를 스스로 생각해 냈겟지. 우리가 배우는 정수론도 누가 만든 거니깐. 근데 imo 수준에서, 저걸 아는 사람들과 상대평가로 대결을 해서 이긴다?(나도 메달은 절평인거 아는데, 선발이나 국가간 대결은 상대평가니깐) 장담하는데 매년 출전자 당 한명씩 있으면 적지 않음. 다 배워서 해내는거임
문제 대부분 저렇게 품. 아이디어 떠올리고 점점 구체화시키고. 만약 이미 잘 정리된 정리가 있으면 그걸 쓰고. 자연스럽게 이어지는거지.