Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Siamese method proof

No description
by

Hongbo Fang

on 28 February 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Siamese method proof

Siamese method proof
1.induction proof: each row add up to correct sum
2.induction proof: each column add up to correct sum
3.ignore diagonal (# -_-)\(^-^ )
4.it is a magic square proof process Required sum: 1 2 3
4 5 6
7 8 9 = (1 + n^2) * n^2 2 From 1 to n^2 1 n * = (1 + n^2) * n 2 sum of all the numbers sum of each row/column Induction proof: each row add up to correct sum:
1. first row equals the that sum equation
2. sum of each row equals sum of first row 3 9 15 16 22
21 2 8 14 20
19 25 1 7 13
12 18 24 5 6
10 11 17 23 4 3 14 30 31 42
41 2 13 24 40
34 100 1 12 23
22 33 44 10 11
20 21 32 43 4 0*n+3 1*n+4 2*n+n 3*n+1 4*n+2
4*n+1 0*n+2 1*n+3 2*n+4 3*n+n
3*n+4 4*n+n 0*n+1 1*n+2 2*n+3
2*n+2 3*n+3 4*n+4 0*n+n 1*n+1
1*n+n 2*n+1 3*n+2 4*n+3 0*n+4 Decimal notation base-5 notation additional notation 18(base-10) = 3*5+3 = 3*n+3 0*n+1 1*n+2 2*n+3 3*n+4 4*n+n
0*n+2 1*n+3 2*n+4 3*n+n 4*n+1
0*n+3 1*n+4 2*n+n 3*n+1 4*n+2
0*n+4 1*n+n 2*n+1 3*n+2 4*n+3
0*n+n 1*n+1 2*n+2 3*n+3 4*n+4 0*n+3 1*n+4 2*n+n 3*n+1 4*n+2 First row: =(1 + .. + n-1)*n + (1 + 2 + .. + n-1 + n)
=(1+n-1)*(n-1)/2 * n + (1+n)*n/2

=(1+n^2)*n/2 Looks familiar (^. ^) n=5 j= 1 2 3 4 n i=1
2
3
4
n E(i,j)=(j-1)*n + ((i+j-2)mod n + 1). E(i+1,j)=(j-1)*n + ((i+j-1)mod n + 1) two cases: E(4,2)=1*n+n
E(5,2)=1*n+1 E(i,j)>E(i+1,j) 1: E(i,j) = (j-1)*n + ((i+j-2)mod n + 1) = (j-1)*n + n (i+1,j) therefore satisfy (i+j-1)mod n = 0 E(i+1,j)= (j-1)*n + ((i+j-1)mod n + 1) = (j-1)*n + 1 (i, j) satisfy (i+j-2) mod n = n-1 E(i+1,j)=E(i,j)-(n-1) 2: Not satisfy the condition above. E(i,j) = (j-1)*n + ((i+j-2)mod n + 1) E(i+1,j) = (j-1)*n + ((i+j-1)mod n + 1) Example: E(i+1,j)=E(i,j)+1 0*n+1 1*n+2 2*n+3 3*n+4 4*n+n
0*n+2 1*n+3 2*n+4 3*n+n 4*n+1
0*n+3 1*n+4 2*n+n 3*n+1 4*n+2
0*n+4 1*n+n 2*n+1 3*n+2 4*n+3
0*n+n 1*n+1 2*n+2 3*n+3 4*n+4 only 1 case n-1 cases case 1: E(I+1,j)=E(I,j)-(n-1) once
case 2: E(I+1,j)=E(I,j)+1 (n-1) times Induction proof: each row add up to correct sum:
1. first row equals the that sum equation
2. sum of each row equals sum of first row
set w(i) = sum of row i in case 1
set m(i) = sum of row i in case 2

w(i+1)=w(i)-(n-1)
m(i+1)=m(i)+1*(n-1) set s(i) = sum of row i

s(i)=w(i)+m(i)
s(i+1)=w(i+1)+m(i+1)
=w(i)-(n-1)+m(i)+1*(n-1)
=w(i)+m(i) So, s(i)=s(i+1) 1 2 3 4 n
n+3 n+4 n+n n+1 n+2
2n+n 2n+1 2n+2 2n+3 2n+4
3n+2 3n+3 3n+4 3n+n 3n+1
4n+4 4n+n 4n+1 4n+2 4n+3 j=1 2 3 4 n i= 1
2
3
4
n E(i,j) = (i-1)n + ((j+2(i-1)-1)mod n +1)
E(i,j)+1 = (i-1)n + ((j+2(i-1))mod n +1) In case of j+2(i-1)-1 = n - 1 ==> j+2(i-1) = n

E(i,j) = (i-1)n + n, E(i,j)+1 = 1(i-1)n + 1
E(i,j+1)+1 = E(i,j)-(n-1)

In other n-1 cases, E(i,j+1) = E(i,j)+1 set s(j) = sum of column j
w=value of first case
m=sum of other case

s(j)=w+m
s(j+1)=w-(n-1)+m+1*(n-1)
=w+m

so, s(j)=s(j+1) sum of first column
(1+n-1)*(n-1)/2*n+(1+n)*n/2
= (n^2+1)*n/2
equals to the required
sum of a magic square Proof process:
1.induction proof: each row add up to correct sum
2.induction proof: each column add up to correct sum
3.ignore diagonal (# -_-)\(^-^ )
4.it is a magic square E(i,j)=(j-i)*n+(3(i-1)+j-1)mod n + 1) one equation to rule them all! i= j=
Full transcript