수열 어려운문제 혹시 푸실수 있는분.. (수능과는 괴리가 있습니다.)

Question

8. 정수 n을 소인수분해했을때 지수가 모두 1인 수를 '예쁜수' 라고 한다.
양의 정수 n에 대하여 Q(n)을 n이하의 양의정수인 예쁜수의 갯수로 정의할 때
Q(n) > n/2 임을 증명하시오.

동아리 주최 퀴즈대회에 나왔던 문젠데요. 
오늘로써 5개월째접어들어감;;..

Redundancy · Accepted Answer

'수리' 게시판 성격과 어울리지 않습니다만, 혹시 괴수분 계실까봐 질문합니다. ㅠㅠ 양해부탁드려요

연설아­ · Answer

n 까지 소수의 개수 a,b,c ... x 까지 있어서 총 x개라고 하면
그 소수들로 만들수 있는 예쁜수는 2^x 개인가요? 근데 그중에 n보다 큰 게 분명 있겠네요
부왘ㅋ 어려워서 이거 .. 아 그리고 1도 빼먹었음

스트라디바리우스 · Answer

1도 예쁜수로 치나보군요. 그렇다고 가정하고 제 풀이 =ㅅ=;;
pf) n 이하의 홀수의 제곱수와 4를 생각해봅시다.
(4, 9, 25,49, 81....)
안예쁜 수는 이런 녀석들중 적어도 하나를 반드시 인수로 갖습니다.

(사실 좀더 타이트하게 얘기하려면 소수의 제곱수를 얘기해야 했지만
굳이 홀수의 제곱수와 4로 얘기한 이유는 풀이를 간단하게 하기 위해..
이렇게 얘기해도 틀린바는 없음)

그런데 이런 4의주기, 9의 주기 등등은 n개의 수중 절반을 덮을만큼
사이클이 빠르지가 않음을 보이면 Q(n) > n/2임을 증명할수 있습니다

다시 말해서, 실제로 안예쁜수의 개수<[n/4]+[n/9]+..... n/2

수열 어려운문제 혹시 푸실수 있는분.. (수능과는 괴리가 있습니다.)

최근 게시글 · 더보기

공부를 도와주는 학습자료