재밌는 문제 풀어보셈요(10.20)(2000덕)
게시글 주소: https://orbi.kr/00069551380
간단한 정수 문제이지만
사실 증명이 메인이라 증명도 간략하게 써주시면 감사하겠습니다!
난이도 :2.5/5
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
국어 연계 8
있잖아뇨,, 국어 69모 1이엇구 기출 2회독 돌렸는데 수특 수완을 풀기만 하는 건...
-
스시랑 우동 시킴 11
흐흐
-
어차피 3대1 3대0은 힘들거라 생각하고 블루에 올인한거 아님?ㅋㅋ
-
현재 매실문 하고 있는데 매실문까지만 하고 모의고사 계속 푸는게 좋을까요 파이널도...
-
걔네 뽑아줬더니 뭔 현실적으로 올해는 무리고 어쩌고.. 하더니 그 해에 학생회...
-
삼도극,무등비 6
이번 수능에 나올거 같으신가요?
-
문과기준 뭐가 더 어렵나요
-
7시간이라 2
치타 지쳤다
-
28,30 1~13번까지 푸는데 20분걸려서 좀 수월하지않았나 싶음 14번은 뭔가...
-
22 킬러는 비주얼부터 심상치 않아서 거를 수 있었음 요즘은 킬러 갖고 ㅈㄹ하니까...
-
아1가 취침 4
-
미소녀 투하 6
-
자릿수는 너무 헷갈려 진짜 아리까리한거 나와서 5분 넘게 쓰고 틀리면 자살마려울듯
-
훈련 편하거나 군수하려고 공군노리는것보단 육군보단 약간 더 수준있는 사람들이랑...
-
찍맛해서 3맞은적은 몇번 있는데 제 실력만으로 푼건 보통 61에서 왔다갔다해요...
-
당신은 미래를 어디까지 보는것입니까...GOAT
-
싱어는 동물 실험이 허용될 수 있긴 하다고 했는데 레건은 동물실험이 어떠한 이유로도...
-
고작 제 수능을 위해 어떤팀은 스위스딱, 어떤팀은 3:1, 어떤팀은 북미한테...
재밌겠군
18?
THANK(땡)
14?
정답!
증명은...?
6⁴ = 1296 < 2077 < 7⁴ = 2401 이므로
6⁴(1296), 5⁴(625), 4⁴(256), 3⁴(81), 2⁴(16), 1⁴(1)
위의 수들의 합으로 2077을 만들어야 함.
1⁴, 2⁴, ..., K⁴들의 합을 이용해 자연수 N을 만들 때
사용된 수들의 최소 개수 : a[N] 이라 하면
a[N] = if(N > i⁴)min(a[N], a[N - i⁴] + 1) (1 ≤ i ≤ K),
a[1⁴] = a[2⁴] = ... = a[K⁴] = 1 로 정의됨.
여기서 N = 2077, K = 6이므로
이를 c++ 코드로 잘 작성해서 돌려보면 a[2077] = 14가 나옴.
역추적까지 해보면
2×5⁴ + 4⁴ + 7×3⁴ + 4×1⁴ = 2077
임을 알 수 있음.
코드풀이는 좀;;
정수로 증명쉽게 되요 ㅋㅋ
풀면서 자꾸 다이나믹 프로그래밍 생각나길래 그만..저도 dp를 모르는게 아닙니다만..허허 수학은 손으로 풀어야된다고욥!
대충 sketch.
2077==13 (mod16)이고, x^4==0or1 (mod16)이므로 n은 최소 13이다.
옙옙