11511 - Frieze Patterns

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

11511 - Frieze Patterns

Post by wahaha » Sat Oct 04, 2008 3:43 pm

i found the period of the numbers is (n+1), but i can not prove it, can anyone help me?
:oops:

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11514 - Frieze Patterns

Post by andmej » Sat Oct 04, 2008 5:54 pm

I have tried too to prove it without success.

What I did in my code was build the table for the first N+1 rows like this:

Code: Select all

f[i][j] = ( f[i+1][j-1] * f[i-1][j] + 1 ) / f[i][j-1];
So we need to prove that

Code: Select all

f[i][j] = f[i][j-N-1] for all j > N + 1
Does anyone have some idea?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

11511 - Frieze Patterns

Post by yiuyuho » Sat Apr 11, 2009 10:18 pm

Problem Link: http://icpcres.ecs.baylor.edu/onlinejud ... 11511.html

Can anyone tell me why the patterns will repeat in exactly n columns?

Post Reply

Return to “Volume 115 (11500-11599)”