아주 어려운 문제 - 아주 큰 수의 끝의 자리 수 구하기

@대박마 어여 풀어주세요.

앗사 나만 당할 수야 없지 

아직 전 문제 못 풀었어여..... 잉잉 10학년도 안됨....

아주 쉬워요 

독백: 이래야 한 삼십분 생각해 보고 생각한 시간이 아까워서 

게속 하더라 

어렵다면 처음부터 안 하더라 

하다가 혼났어요.. ㅋㅋ

이과 망했으면...

소근소근 이과 망하게 하려는 무시븐 문과의 의도....

짝퉁 이과는 대장균 꼬리 갯수 세러 갑니다...

꼬리가 잇어요? 

그리고 잇다 쳐도 하나가 아녀요? 아이고 

*대장균 주의*

https://www.google.com/search?q=escherichia+coli&client=safari&hl=en-us&prmd=ibnv&source=lnms&tbm=isch&sa=X&ved=0ahUKEwie58HDv9LgAhUShuAKHRQzA2sQ_AUIEigB&biw=1024&bih=666

원래 수학쪽이 유사이과고 진짜 이과는 물리, 화학, 생물 아닌가요?

쉿! 그러시면 수학 못해서 도망가는거 들키잖아요...

애 수영하는 거 안보고 마모 한다고 보스님께 혼남......

디오게네스의 용기를 본받으시오

나는 보스다 

나는 대박마다 

내가 무섭지 않은가 

아니긴 졸라 무섭다 

그대는 선한 자인가 

그렇다 

그렇다면 선한 자가 애 수영하는데 마모를 하는가 

시정하겟다 

그의 명성은 자자하여서, 알렉산드로스 대왕이 디오게네스를 찾아온 일이 있었다. 그는 양지 바른 곳에서 일광욕을 즐기고 있었다.
"나는 알렉산드로스, 대왕이다."
"나는 디오게네스, 개다."
"내가 무섭지 않은가?"
"그대는 선한 자인가?"
"그렇다."
"그렇다면 뭣 때문에 선한 자를 두려워 하겠는가?"
이에 알렉산드로스가 "소원이 있으면 말하라"라고 하니, 디오게네스는 "햇빛을 가리지 말고 비켜달라"고 대답했다. 무례한 저 자를 당장 처형해야 한다고 나서는 부하들에게, 알렉산드로스는 "내가 만약 알렉산드로스가 아니었다면, 디오게네스가 되고 싶었을 것이다."라고 말하며 그들을 말렸다. 

둘이 대화전에 각본 짠것같음.

ㅋㅋ 

알렉산더가 쇼한거 같죠 

나는 관대하다 할라고 

설마요....

나중에 사람들이 재 구성 한거겠죠...

단군신화...

정몽주 이방원처럼.....

a_{n+1} - a_n을 인수분해 비슷하게 하면 

= 3^(a_n) - 3^(a_{n-1}) = 3^(a_{n-1}) * 2 * (3^(a_n - a_{n-1}- 1 ) + ...+ 3 + 1) 가 되는데

제일 오른쪽 괄호가 3의 승수들을 뺑뺑이 돌리면서 더하는거니까 끝자라가 제일 오른쪽부터 1,3,9,7,1,3,9,7... 이렇게 되고

고렇게 더한 애들이 자연수*10^(n-1) 개 있으니까, 앞의 자연수 떼고 생각하면서 (수학적 귀납법 가정) 4개씩 짝 지으면 25*10^(n-3)*(40*큰수+ 1+3+9+7) = 5* 10^(n-1)이 되서 저 앞의 2 곱한거 까지 치면 10^n이 되서 차이가 10의 n승이니 끝의 n자리가 같고, 블라블라...

핸드폰으로 기호까지 치려니까 너무 골치 아프네요. 대충 이런 식인데 꼼꼼하게 경우 따져가면서 하면 될 듯 해요. 별로 우아하진 않네요. 

좀 이상한데요 

3^27 의 다음 수는 

(3^3)^27 이 아니라 

3^(3^27) 

훨씬 커요 

저 첫 식 제일 오른쪽 긴 괄호가 그만큼 긴거라서... 맞는거 같은데, 아닌가요?

3^(3^27) - 3^27 하면 어떻게 된다구요? 

3^27 * (3^(3^27 -27) - 1) = 3^27 * (3 - 1) * ( 3^(3^27 -27 - 1) + 3^(3^27 -27 - 2) + ... + 3^2 + 1)  이렇게 되는거 같은데...

긴 괄호 안에 (3^27 -27) = 3^27 - 3^3 개 (10의 배수)의 항이 들어있고요. 

짝짝 멋집니다. 

설명 좀 해 주세요 

굽신굽신 

이해가 아직 안 가요 

아... (x^n - y^n)을 인수분해인지 뭔지 하면 (x-y)*(x^(n-1)*y+ x^(n-2)*y^2 + ... + x^2 * y^(n-2) + x * y^(n-1) + y^n)으로 표현할 수 있잖아요.

3^(3^27 -27) - 1 을 3^(3^27 -27) - 1^(3^27 -27) 로 보면, (즉, x=3, y=1, n=3^27 -27)

(3 - 1) * ( 3^(3^27 -27 - 1) + 3^(3^27 -27 - 2) + ... + 3^2 + 1) 이렇게 쓸 수 있다는 뜻이었어요.

수영장 갔다가 와서 전기장판과 일체 후.....벌써 답이 나왔네요. 멋짐 하나 드립니다...

감사합니다. 근데 아직 안 "낫어요".  맞는 것 같나요?

전 바로 아들 라이드 다니느라 검산도 못 하고...

맞는 것 같은데여. 히고님 식사중?

아님 라이드?

저두 또 라이드 가야 합니다.

하루 일과가 운전과 전기장판...... ㅋㅋ

@Prodigy 님 소환해봅니다.

ㅎㅎㅎ 위에 답이 맞는거 아닌가요? 맞는거 같은데요. 풀이 멋집니다 ㅎㅎ

@Prodigy 님이 맞다니까 정말 맞나보네요. 꼼꼼하게 못 따져보고 후다닥 올린 다음에 계속 기사 노릇하느라 종이에 못 적어봤어서 확신이 없었는데, 확인해주셔서 감사합니다.

아....저도 오늘은 마모할 시간이 많이 없어서 그냥 쭉 보고 이거 맞지 않나 하고 넘어갔는데요. -.-;; 저도 제대로 본건 아니에요. 근데 일단 문제출제자가 났다고 해서요 ㅎㅎ

아줌마 낫어요! 

beautiful ! 

전 훨씬 복잡하게 풀엇는데 

훨씬 간단하네요 

glad I asked, thanks ! 

진짜 궁금한게 이런 거 어디서 알아 오시나여?

애들 엄마: 야 이거 풀어 

애들: 아빠 이거 너무 어려워 

나: 낑낑

나만 당할 수는 없지 

여러분 이거 쉬워요! 

쏘스는 뭐 amc aime 어디 경시대회 문제 

학교에서 누가 자랑한 문제 

학교 선생이 자랑한 문제 

어디 주말 학교 여름 학교 선발 고사 문제 

사모님 대단하시네요. _^부럽....

소곤소곤 

맨 밑줄은 지워요 

저도 목숨은 아까운지라 

니 소원은 무엇이냐 

오래 살고 싶습니다 

방금 큰노무시키 한테 물어 봤습니다. 혹시 AMC 아냐고 그랬더니...

큰노무시키: 아 그거 선생님이 신청하라고 했는데 까먹었어. 그래서안해.....

아 속 뒤비집니다.....

피천득: 마지막 질문은 아니 물엇어야 좋앗을 것이다 

마모 폭파하고 싶은 아이가 

한명 늘엇어요 

독일 있을때는 선생님이 신청 해주고 데려가 시험보게 했는데.... 미국은 나라가 커서 그런지.... 신경도 안쓰시네여.... 하긴 하시는 일도 많으실텐데 빨짓거리 하는 십대... 저라도 신경 안 쓰이겠네여.....

속으로 혼자 이야기 합니다. 아들아 그래도 아빠가 사랑해.....

ㅋㅋ 

미국은 자유가 중요해서 나라에서 뭐 하자면 

싫어! 가 많아서 그렇게 못해요 

우리 주 레벨에서 커리큘럼 정할까 

싫어! 

우리 국민 건강 보험할까 

싫어! 

우리 학교에서 학생들 전부 백신 맞힐까 

싫어! 

우리 매년 주내 학년별로 학력 검정 시험 볼까? 

싫어 ! 

울 큰나무시키가 제가 뭐라고 말하면 하는 말인데요.. ㅋ

싫어.... 

그럼 반대로 물으면 되겟네요 

그 간단한걸 가지고 

제일 오른쪽 괄호가 3의 승수들을 뺑뺑이 돌리면서 더하는거니까 끝자라가 제일 오른쪽부터 1,3,9,7,1,3,9,7... 이렇게 되고

고렇게 더한 애들이 자연수*10^(n-1) 개 있으니까, 앞의 자연수 떼고 생각하면서 (수학적 귀납법 가정) 4개씩 짝 지으면 25*10^(n-3)*(40*큰수+ 1+3+9+7) = 5* 10^(n-1)이 되서 저 앞의 2 곱한거 까지 치면 10^n이 되서 차이가 10의 n승이니 끝의 n자리가 같고, 블라블라... 

애가 이거 틀리다고 지적 

끝자리가 1 3 9 7 로 끝나고 이게 1000 쌍이면 

이 숫자가 20*1000 의 배수냐고 

아니라고 

생각해 보니 아녀요 

이게 될라면 십 백 .. 자리수가 다 0 이거나 

더해서 이쁘게 0 이 되야 한다고 

듣고 보니 맞는말 

다시 푸시오 

아이고 저기 40*큰수가 아니라 10*큰수 밖에 안 되네요. 

신새벽에 이게 웬 날벼락이...

정자세로 책상 앞에 앉을 시간이 없는데 주말에 애 라이드하는 중간중간 다시 볼게요. 

그 전에 그걸 캐치해낸 똑똑한 10학년 학생이 풀어주면 좋겠네요. ㅋㅋㅋ

ㅋㅋ 글게요.... 맨땅에 헤딩을 많이 해서.... 영 상태가..... ㅋㅋ

오늘의 수학 문제 

@무지렁이 우승하셧구요 

감동임다 

저희는 내일도 최선을 다하겟슴다 

무지렁이 님께서 먼저 푸셨지만 이렇게 하면 증명이 좀 간단할 것 같아서요:

3^4 mod 4 = 1, 3^4 mod 10 = 1

a_n mod 4 = 3 이라고 했을 때 a_(n+1) mod 4 = 3^a_n mod 4 = 3^3 mod 4 = 3, 그리고 a_(n+1) mod 10 = 3^a_n mod 10 = 3^3 mod 10 = 7

a_0 = 3, 따라서 a_n (for n >= 1) mod 10 = 7

되는거 맞나요?

a_n (for n >= 1) mod 10 = 7 

이건 맞구요 

문제는 

a_(n+1) = a_n mod 10^n 

이걸 보이라는 거여요 

즉 끝의 n자리수가 같다 

앗 대충보고 이상한 문제 풀었네요! 댓글 안단걸로...

ㅋㅋ 

마지막 자리가 다 7 이라는게 결과의 일부죠 ㅋㅋ 

시작이 반 

좀 더 적어보면 a1 끝자리 7 

a2 끝자리 87 

a3 끝자리 387 

a4 끝자리 5387 

이렇게 가요 

좀 구먹구구식이긴 한데, 어쨌든 증명은 증명이라 올려봅니다.

우선 F_n(M) = last n-digit integer of an integer M 이라고 정의하면, 

정수 M을 마지막 n 자리수 (b) 와 그 앞의 큰 수(a X 10^n) 로 쪼개서 표현해서,

M = a X 10^n + b  (for b < 10^n)

이렇게 쓰면 b = F_n(M) 이고, 일반적으로 F_n(aX10^n+b)=F_n(b) 를 만족합니다.

보조정리 2개 (증명은 나중에)를 이용할건데요.

보조정리1 (L1): 

F_n(M_1 M_2) = F_n( (F_n(M_1) F_n(M_2) )

보조정리2 (L2):

For n>=2, F_{n+1}(3^(aX10^n)) = 1  (for any interger a >=0)

(따라서 F_n(3^(aX10^n)) = 1 도 됩니다.)

그러면 문제를 위에 정의한 함수 F_n을 이용해서 다시 쓰면,

a_n 을 다음과 같이 정의했을때,

a_0=3

a_{n+1}=3^a_n

F_n(a_{n+1}) = F_n(a_n) 을 보이면 되겠네요.

즉 a_{n+1) 의 마지막 n 자릿수가 a_n 의 마지막 n 자릿수와 같음을 보이면 됩니다.

수학적 귀납법을 써서,

For n=1;

a_1=3^3=27 --> F_1(a_1)=7

a_2=3^27 = 3^24 X 3^3

F_1(a_2) = F_1( F_1(3^24) F_1(3^3) ) = F_1( 1 X 7 ) = 7 = F_1(a_1)

n>=2 인 경우에 대한 증명:

F_k(a_{k+1}) = F_k(a_k) 이 참이라고 가정하고

F_{k+1}(a_{k+2}) = F_{k+1}(a_{k+1}) 을 보이면 됩니다.

우선 a_n을 마지막 n 자리수 (c_n) 와 그 앞의 큰 수(b_n X 10^n) 로 쪼개서 표현해서,

a_n = b_n X 10^n + c_n where c_n = F_n(a_n) 

(LHS) 

F_{k+1}(a_{k+2})

    = F_{k+1}(3^a_{k+1})

    = F_{k+1}( 3^(b_{k+1} X 10^{k+1} + c_{k+1}) ) 

    = F_{k+1}( 3^(b_{k+1} X 10^{k+1}) X 3^c_{k+1}) ) 

    = (by L1) F_{k+1}( F_{k+1}( 3^(b_{k+1} X 10^{k+1} ) F_{k+1}(3^c_{k+1}) )

    = (by L2) F_{k+1}(3^c_{k+1})

    c_{k+1} 는 a_{k+1} 의 마지막 (k+1) 자릿수이므로, 

        첫번째 digit과 마지막 k 자릿수로 나눠서 표현하면, 

    c_{k+1} = p X 10^k + q 

        여기서 마지막 k 자릿수 q = F_k(c_{k+1}) = F_k(a_{k+1})

        이고, 수학적 귀납법의 전제인  F_k(a_{k+1}) = F_k(a_k) 을 이용해서 

    q = F_k(a_k) = c_k

    Then 

    F_{k+1}(a_{k+2}) = F_{k+1}( 3^(p X 10^k + q) )

        = F_{k+1}( 3^(p X 10^k) X 3^q) )

        = (by L1) F_{k+1}( F_{k+1}( 3^(p X 10^k) F_{k+1}(3^q) )

        = (by L2) F_{k+1}(3^q) = F_{k+1}(3^c_k) 

(RHS)

F_{k+1}(a_{k+1})

    = F_{k+1}( 3^(b_k X 10^k + c_k ))

    = F_{k+1}( 3^(b_k X 10^k) X 3^c_k ))

    = (by L1) F_{k+1}( F_{k+1}(3^(b_k X 10^k)) F_{k+1}(3^c_k) )

    = (by L2) F_{k+1}(3^c_k)

Therefore, (LHS)=(RHS). 

Q.E.D.

보조정리1: F_n(M_1 M_2) = F_n( (F_n(M_1) F_n(M_2) )

증명: 

    M_1 = a_1 X 10^n + b_1  (b_1 = F_n(M_1))

    M_2 = a_2 X 10^n + b_2  (b_2 = F_n(M_2))

    M_1 M_2 = a_1 a_2 X 10 ^{2n} + (a_1 b_2 + a_2 b_1)X10^n + b_1 b_2

            = ( a_1 a_2 X 10^n + a_1 b_2 + a_2 b_1) X 10^n + b_1 b_2

    -> F_n(M_1 M_2) = F_n(b_1 b_2) = F_n( (F_n(M_1) F_n(M_2) )

보조정리2: For n>=2, F_{n+1}(3^(aX10^n)) = 1  (for any integer a >=0)

증명:

    3^(aX10^n) = 3^(100XaX10^(n-2)) = (3^100)^(aX10^(n-2)) 

    3^100 = p X 10^3 + 1  <-- used F_3(3^100)=1 

    (3^100)^(aX10^(n-2)) = ( p X 10^3 + 1 )^(aX10^(n-2)) 

    = 1 + (aX10^(n-2))X(pX10^3) + (aX10^(n-2))(aX10^(n-2)-1)/2 (pX10^3)^2 + ...

    = 1 + apX10^(n+1) + (a p^2)(aX10^(n-2)-1)/2 10^(n+4) + ...

    = 1 + (ap + (a p^2)(aX10^(n-2)-1)/2 10^3 +...)X10^(n+1)

    --> F_{n+1}(3^(aX10^n)) = 1  

너무 주먹구구식으로 증명을 해놔서, 다른 분들이 보기엔 좀 불편할거 같네요. 

더 간단한 방법이 있을듯 한데, 전 못 찾겠네요.

@무지렁이 @레모네이드 

무지렁이 식을 처음 이쁘게 쓰다: 시작이 반 

a_{n+1} - a_n = 3^(a_n) - 3^(a_{n-1}) = 3^(a_{n-1}) *[3^(a_n - a_{n-1}) -1 ]

점화식이죠 

보기 좋게 쓰자면 

a3-a2 = 3^a2 - 3^a1 = 3^a1* [3^(a2-a1)-1] 

이렇게 진행하는 

근데 

@레모네이드 님도 같은 말씀인데 

3^천의배수- 1 = 만의배수 

3^만의배수-1 = 십만의배수 

.... 

이게 되요, 오마이! 이게 되면 위에 것이 줄줄이 되죠 

다만, 3^십의배수 -1 = 백의배수 이건 안되고 

3^이십의배수 -1 = 이백의배수 

이게 되요 

이게 왜 되냐면 가령 

3^1000 -1 = (3^100 -1 ) * (3^900 + ... + 3^100 + 3^0) 

인데 (3^100 -1 ) = 천의 배수 

(3^900 + ... + 3^100 + 3^0) =끝자리1 인 숫자가 열개 = 십의 배수 

고로 

3^1000 -1 = 만의 배수 

이렇게 줄줄이 비엔나 

다만 3^100 -1 = (3^20 -1) *(3^80 + 3^60 + ... + 3^20 + 1) = 200의 배수 * 5의 배수 = 천의 배수 

근데 처음 숫자가 

a2-a1 = 3^27 - 3^3 = 20의 배수, 고로 a3-a2 = 백의 배수, a4-a3=천의 배수, ...

QED

위에 @무지렁이 님이 쓴 걸 잘 안보고 무대뽀로 증명하다보니 쓸데없이 복잡해졌네요.

보조정리2를 이용해서 a_{n+1}-a_n 이 10^n 의 배수인 걸 보이는게 훨씬 간단했겠네요.

잘 정리해주셔서 감사합니다. 역시 문과...