PE 71 72 73 Farey Neighbours (sequence) (farey序列)

电玩女神 2022-07-15 10:57 29阅读 0赞

Patrick from Woodbridge School proved the first part of this question:  
  
If 0<*b**d*<*a**c*<1 then *b**c*<*a**d* . Adding *b**d* to both sides of the inequality gives *b*(*c*\+*d*)<*d*(*a*\+*b*), while adding *a**c* to both sides gives *c*(*a*\+*b*)<*a*(*c*\+*d*). So it follows that

*b**d*<*a*\+*b**c*\+*d*<*a**c*.

We know *F*1=01,11 and *F*2=01,12. The mediant of 01 and 12 is 13 and the mediant of 12 and 11 is 23. So

*F*3=01,13,12,23,11.

The mediant of 01 and 13 is 14. The mediant of 13 and 12 is 25 and so is not included in *F*4. The mediant of 12 and 23 is 35 and so is not included in *F*4. The mediant of 23 and 11 is 34. Thus

*F*4=01,14,13,12,23,34,11.

The mediants of *F*4 are : 15, 27 (not included in *F*5), 25, 35 , 57 (not included in *F*5) and 45. Therefore

*F*5=01,15,14,13,25,12,35,23,34,45,11.

Edd from Sidcot school did the first part in a similar way and used mathematical induction to prove that, in every Farey sequence, if *b**d* and *a**c* are consecutive terms (said to be Farey neighbours) then |*a**d*−*b**c*|=1.  
First *F*1=01,11 and ![gif.latex_7Cad-bc_7C_3D_7C1-0_7C_3D1][],so the result is true for *n*=1.  
  
Assuming the result for *F**n* we next prove that the result follows for *F**n*\+1.  
We have *F**n*=…*b**d*,*a**c*… and |*a**d*−*b**c*|=1.  
If *d*\+*c*≤*n*\+1 then *F**n*\+1=…*b**d*,(*b*\+*a*)(*d*\+*c*)*a**c*… and |*d*(*b*\+*a*)−*b*(*d*\+*c*)|=|*a**d*−*b**c*|=1. The only other possibility is that *d*\+*c*>*n*\+1 in which case *F**n*\+1=…*b**d*,*a**c*… with |*a**d*−*b**c*|=1, so the result is true for *n*\+1.  
  
Hence, by the axiom of induction the result is true for all positive integer values of *n* .

**Wiki:[Farey\_sequence][Farey_sequence] (点击)**

**[点击打开链接][Link 1]**

**推荐题目**

PKU 2478 Farey Sequence

TJU 2798 Farey Sequence

PKU 3374 Cake Share

PE 71 PE 72 PE 73

[gif.latex_7Cad-bc_7C_3D_7C1-0_7C_3D1]: /images/20220715/4d130464bf7e47ca927bb8399e5dc523.png
[Farey_sequence]: https://en.wikipedia.org/wiki/Farey_sequence
[Link 1]: http://nrich.maths.org/6598/solution