문제투척

89인가요? 피보나치수열하고 관련된것같은데...

흐흐흐

마디 하나당 두 개의 꼭짓점이 필요하고

마디들은 서로 꼭짓점을 공유하지 않고,

20개의 꼭짓점 중에서 10개의 마디를 만들어야 하니까

실제로 대각선 마디는 있으나 마나고

ㅣ 아니면 = 로만 해야 하니까..

처음에 2n개의 꼭짓점이 있을 때 조건을 만족하도록 하는 가짓수를 a_n이라 두면

ㅣ ...

= ...

에서 a_n+2 = a_n+1 + a_n

a_1 = 1, a_2 = 2 이고

{a_n} : 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

에서 a_10 = 89



인데

피보나치 수열은 a_n+2 = a_n+1 + a_n 이 점화식에 a_1 = 1, a_2 = 1 일 때이고,

a_n+2 = a_n+1 + a_n, a_1 = 1, a_2 = 3 인 경우만 하더라도 피보나치 수열이 아니라 루카스 수열..

에서 처럼 엄밀하게는 피보나치 수열이 아니라 점화식만 공유한다고 볼 수 있지 않을까요..

A2 =3 아닌가요??

앜, 그러고보니 대각선이 필요없는게 아니었군요ㅠ_ㅜ..

A2 = 3 으로 두고 점화식 다시 세워야 할듯;

피보나치 수열은 아니네요
점화식이 디게 복잡하네요

l...

=...

X...

에서 a_n+2 = a_n+1 + 2a_n, a_1 = 1, a_2 = 3

a_n+2 - pa_n+1 = q(a_n+1 - pa_n)

p + q = 1

pq = -2

에서 점화식 세우는 것보다

걍 나열해서 찾는게 빠를거 같네요.

{a_n} : 1, 3, 5, 11, 21, 43, 85, 171, 341, 683

에서 683

포함하는 경우이긴 한데,

적절히 수치를 평행이동해서 받아들이면 될거 같아요,

제 논리가 틀리지 않았다면;;

683 인가요??

아 늦었네여.....

x0에서부터 차근차근 생각해보면, x0은 반드시 어딘가의 점과 하나의 마디로 연결되어 있어야 하잖아요.
x0이 x1과 연결되었을 때(마디선이 수평으로 갔을 때), y0도 반드시 하나의 점과 연결되어 있어야 하는데
x0은 이미 x1과, x1도 이미 x0과 연결되어 있으므로 y0은 y1과밖에 연결될 수가 없죠
이렇게 네 점을 연결하고 나면 이 네 점은 이미 조건을 충족시켰으므로 제외시키고 생각하면, x2, y2부터 시작해서
xn. yn 에서 끝나는 문제가 하나 더 만들어지죠. 이 경우는 마디를 2개 그었으므로 (n-1)개의 마디를 (2n-2) 개의 점에 연결시킨다
라고 생각하면 An-2가 되죠.

An = 2^(n+2) / 3 + 1/3 x (-1)^(n+1)

후하.. 일반항까지 구하셨네요 ㅋㅋ

앜,, 첨에 0부터 시작하는걸 보정하셔서 답 구하셨네요 ㅎ_ㅎ;

요게 정답.

아 그리고 위에 (p, q) = (2, -1) or (-1, 2)가 나오니까

a_n+2 - 2a_n+1 = -(a_n+1 - 2a_n), a_2 - 2a_1 = 1 에서 a_n+1 - 2a_n = 1*(-1)^n-1 = -(-1)^n

a_n+2 + a_n+1 = 2(a_n+1 + a_n), a_2 + a_1 = 4 에서 a_n+1 + a_n = 4*2^n-1 = 2*2^n

3a_n = 2^n+1 - (-1)^n+1

∴ a_n = {2^n+1 - (-1)^n+1}/3

해도 결과는 같게 나오는거 같네요;;