Một số ứng dụng của giải tích trong đại số, hình học, số học và toán rời rạc - Nguyễn Văn Mậu

3) (14) (15) 4f f f f f f f f         2 2 2 2 2 2 2 2 (1000 ) (1001 ) (1010 ) (1011 ) (1100 ) (1101 ) (1110 ) (1111 ) 4. f f f f f f f f         §iÒu nμy dÉn ta ®Õn Qui luËt: ( )f n chÝnh lμ sè ch÷ sè cña n viÕt trong hÖ nhÞ ph©n. Chøng minh: Kh¼ng ®Þnh trªn ®óng cho 1, 2, 3,...,15n  hay 0 42 2n  . Ta sÏ chøng minh b»ng qui n¹p theo q nh− sau. Gi¶ sö 12 2q qn   , khi Êy trong hÖ c¬ sè 2 th× n sÏ cã 1q  ch÷ sè. NÕu 2n m th× 12 2q qm   vμ m cã q ch÷ sè trong hÖ c¬ sè 2. Theo gi¶ thiÕt qui n¹p ( )f m q . Do ®ã theo ®Çu bμi ta cã ( ) 1 ( ) 1 ( ) 1 2 nf n f f m q      . NÕu 2 1n m  th× 12 1 2 1 2 2 q q m    . Do m lμ sè nguyªn nªn 12 2q qm   vμ m còng sÏ cã q ch÷ sè trong c¬ sè 2. Theo gi¶ thiÕt qui n¹p ( )f m q . Do ®ã theo ®Çu bμi ta l¹i cã 1( ) 1 ( ) 1 ( ) 1 2 nf n f f m q      . 208 Nh− vËy, trong mäi tr−êng hîp ta ®Òu cã ( )f n b»ng chÝnh sè ch÷ sè cña n viÕt trong c¬ sè 2. Bμi to¸n 3. Gi¶ sö :f N N lμ hμm sè tho¶ m·n (1) 1f  , (2 ) ( )f n f n vμ (2 1) (2 ) 1f n f n   víi mäi sè nguyªn d−¬ng n . T×m gi¸ trÞ lín nhÊt cña ( )f n trong kho¶ng 1 2006n  . Gi¶i: V× (2 )f n ®−îc tÝnh theo ( )f n vμ (2 1)f n  ®−îc tÝnh theo (2 )f n , tøc lμ l¹i theo ( )f n , nªn ta nghÜ tíi chuyÖn viÕt c¸c sè trong c¬ sè 2. Ta tÝnh: 2(10 ) (2) (2.1) (1) 1f f f f    ; 2(11 ) (3) (2.1 1) (2) 1 2f f f f      ; 2(100 ) (4) (2.2) (2) 1f f f f    ; 2(101 ) (5) (2.2 1) (2) 1 2f f f f      ; 2(110 ) (6) (2.3) (3) 2f f f f    ; 2(111 ) (7) (2.3 1) (3) 1 3f f f f      ; 2(1000 ) (8) (2.4) (4) 1f f f f    ; 2(1001 ) (9) (2.4 1) (4) 1 2f f f f      ; 2(1010 ) (10) (2.5) (5) 2f f f f    ; 2(1011 ) (11) (2.5 1) (5) 1 3f f f f      ; 2(1100 ) (12) (2.6) (6) 2f f f f    ; 2(1101 ) (13) (2.6 1) (6) 1 3f f f f      ; 2(1110 ) (14) (2.7) (7) 3f f f f    ; 2(1111 ) (15) (2.7 1) (7) 1 4f f f f      ; 2(10000 ) (16) (2.8) (8) 1f f f f    ; 2(10001 ) (17) (2.8 1) (8) 1 2f f f f      . Tõ ®©y ta rót ra qui luËt sau. 209 Quy luËt: ( )f n b»ng sè ch÷ sè 1 trong biÓu diÔn c¬ sè 2 cña n . Chøng minh: Gi¶ sö kh¼ng ®Þnh ®óng víi mäi k n . Ta sÏ chøng minh nã ®óng víi n . NÕu n ch½n th× 22 10n m m   . V× trong hÖ c¬ sè 2, khi nh©n mét sè víi 22 10 , ta chØ viÖc thªm sè 0 vμo cuèi sè ®ã nªn m vμ 210n m  cã cïng sè ch÷ sè 1 trong biÓu diÔn c¬ sè 2. Theo gi¶ thiÕt quy n¹p, ( )f m b»ng ®óng sè ch÷ sè 1 cña m , mμ ( ) (2 ) ( )f n f m f m  nªn ( )f n còng b»ng ®óng sè ch÷ sè 1 cña m , tøc lμ còng b»ng ®óng sè ch÷ sè 1 cña n . NÕu n lÎ, tøc lμ 22 1 10 1n m m     th× n cã sè ch÷ sè 1 nhiÒu h¬n m lμ 1 ch÷ sè (thªm ch÷ sè 1 ë hμng cuèi cïng, tøc lμ ë hμng ®¬n vÞ). Theo ®Çu bμi ta cã ( ) (2 1) ( ) 1f n f m f m    , mμ theo quy n¹p, ( )f m b»ng ®óng sè ch÷ sè 1 cña m nªn ( )f n còng b»ng sè ch÷ sè 1 cña m céng thªm 1, tøc lμ ( )f n còng b»ng ®óng sè ch÷ sè 1 cña n . Bμi to¸n dÉn ®Õn ph¶i t×m sè cã sè ch÷ sè 1 lín nhÊt trong biÓu diÔn c¬ sè 2 cña c¸c sè nhá h¬n 2006. V× 11211111111111 2 1 2047   gåm 11 ch÷ sè 1, mμ 2006 2047 nªn ( )f n cã nhiÒu nhÊt lμ 10 ch÷ sè 1. Ta l¹i cã 2(1023) (1111111111 ) 10f f  . Do ®ã gi¸ trÞ lín nhÊt cña ( )f n trong kho¶ng 1 2006n  lμ 10 ®¹t ®−îc khi 1023n  . Bμi to¸n 4. Gi¶ sö  nx lμ d·y sè x¸c ®Þnh theo c«ng thøc truy håi 0 10; 1x x  vμ 11 2n nn x xx   . Chøng minh r»ng d·y sè nμy héi tô vμ t×m giíi h¹n cña chóng. 210 Gi¶i: Ta tÝnh nx vμ biÓu diÔn chóng trong c¬ sè 2: 2 2 1 0,1 2 x   ; 3 2 11 32 0,75 0,11 2 4 x      hoÆc lμm phÐp céng trong hÖ c¬ sè 2 (chia mét sè viÕt trong c¬ sè 2 cho 2 ta chØ viÖc dÞch dÊu phÈy ®i mét ®¬n vÞ vÒ bªn ph¶i): 1 2 2 2 2 3 2 1 0,1 1,1 0,11 2 2 2 x xx      ; 4 2 1 3 52 4 0,625 0,101 2 8 x      hoÆc 2 3 2 2 24 2 0,1 0,11 1,01 0,101 2 2 2 x xx      ; 5 2 3 5 114 8 0,1011 2 16 x     hoÆc 3 4 2 2 25 2 0,11 0,101 1,011 0,1011 2 2 2 x xx      ; 6 2 5 11 218 16 0,65625 0,10101 2 32 x      hoÆc 4 5 2 2 26 2 0,101 0,1011 1,0101 0,10101 2 2 2 x xx      . Tõ ®©y ta rót ra qui luËt: 2 20,101010...101kx  víi 1k  cÆp sè 10 vμ ch÷ sè 1 ë cuèi; 2 1 20,101010...1011kx   víi 1k  cÆp sè 10 vμ sè 11 ë cuèi. ThËt vËy, theo qui n¹p ta cã 2 2 1 2 2 2 2 2 2 0,101010...101 0,101010...1011 2 2 1,010101...0101 0,101010...101 2 k k k x xx       víi k cÆp sè 10 vμ ch÷ sè 1 ë cuèi; T−¬ng tù, 211 2 1 2 2 2 2 2 3 2 2 0,101010...1011 0,101010...101 2 2 1,010101...01011 0,101010...1011 2 k k k x xx        víi k cÆp sè 10 vμ ch÷ sè 11 ë cuèi. §Ó tin t−ëng vμo kÕt qu¶ trªn, tèt nhÊt lμ ®Æt hai sè 2kx vμ 2 1kx  (hoÆc 2 1kx  vμ 2 2kx  ) thμnh cét vμ céng hμng däc cã nhí trong c¬ sè 2 nh− sau: 2 20,101010...101kx  2 1 20,101010...1011kx   -------------------------------- 1,01010101012 VËy 2 2 2 21,01010...10101 : 2 0,101010...101kx    . T−¬ng tù cho 2 3kx  : 2 1 20,101010...1011kx   2 2 20,101010...10101kx   -------------------------------- 1,010101010112. VËy 2 3 2 21,01010...101011 : 2 0,101010...1011kx    . Tõ ®©y ta cã 2 2 2 2 2 2 1 0,101010...101 0,101010...100 0,00...001 10,101010...100 2 k k x       vμ 2 1 2 2 2 2 2 1 2 0,101010...1011 0,101010...1010 0,00...0011 1 10,101010...1010 . 2 2 k k k x         Mμ 2 1 2 1 2 1 1 1lim lim( ) 0 2 2 2k k kk k      nªn  2 2 2lim lim 0,1010...10 0,101010... 3nn nx    . 212 C¸ch 2 (tÝnh to¸n trong c¬ sè 10): Ta cã: 2 1 2 x  ; 3 11 1 12 2 2 4 x     ; 4 1 1 1( ) 1 12 2 4 2 2 8 x      ; 5 1 1 1 1( ) ( ) 1 1 12 4 2 8 2 2 8 16 x        ; 6 1 1 1 1 1( ) ( ) 1 1 12 8 2 8 16 2 2 8 32 x         ; Ta sÏ chøng minh c«ng thøc sau b»ng qui n¹p: 2 3 5 2 3 2 1 1 1 1 1 1... 2 2 2 2 2n n n x        ; 2 1 3 5 2 3 2 1 2 1 1 1 1 1 1... 2 2 2 2 2 2n n n n x          . ThËt vËy, gi¶ sö c«ng thøc trªn ®óng víi mäi k n . Ta cã 2 2 1 2 2 3 2 1 3 2 1 2 2 1 1 1 1 1 1 1( ... ) ( ... ) 2 22 2 2 2 2 2 n n n n n n x xx              3 2 1 2 1 1 1 1 1( ... ) 2 2 2 2n n       . vμ 2 1 2 2 2 3 3 2 1 2 3 2 1 2 1 3 2 1 2 1 2 2 2 1 1 1 1 1 1 1 1( ... ) ( ... ) 2 22 2 2 2 2 2 2 1 1 1 1 1( ... ) . 2 2 2 2 2 n n n n n n n n n n x xx                          VËy c«ng thøc truy håi ®−îc chøng minh. Ta cã 213 2 3 5 2 3 2 1 2 2 4 2 4 2 2 2 2 1 1 1 1 1... 2 2 2 2 2 111 1 1 1 1 1 2 12(1 ... ) (1 ).12 2 32 2 2 2 21 2 n n n n n n n x                      vμ 2 1 3 5 2 1 2 2 2 1 1 1 1 1 2 1 1... (1 ) 2 32 2 2 2 2 2n n n n n x           . VËy 2lim 3nn x  . Lêi b×nh: Thùc chÊt hai c¸ch gi¶i trªn lμ mét. Bμi to¸n 5 (V« ®Þch Quèc tÕ lÇn thø 10, 1968) Chøng minh r»ng víi mäi sè tù nhiªn n , 0 1 2 1 2 3 2 2 2 ... 2 2 2 n n n n                      . (*) Gi¶i: Ta sÏ sö dông c¬ sè 2 vμ chøng minh ®¼ng thøc (*) b»ng quy n¹p theo n . NÕu 21 1n   th× ®¼ng thøc hiÓn nhiªn ®óng. NÕu 2n  th× do 1 1 2 2 2 2 21 0 2 2 k k k k        ®óng víi mäi 2,3,4,...k  nªn 2 1 3 1 2 2 2 2 2 20 ... ... 2 2 2 k k k k                         víi mäi 2,3,4,...k  VËy 0 1 2 1 2 3 2 2 2 2 2 2 ... 2 2 2 2                      hay bÊt ®¼ng thøc (*) ®óng víi 2n  . Gi¶ sö ®¼ng thøc ®óng víi mäi sè nhá h¬n n . Ta sÏ chøng minh nã ®óng cho n . 214 NÕu 2n m hoÆc 2 1n m  th× m trong c¬ sè 2 chÝnh lμ sè nhËn ®−îc tõ n sau khi xãa ch÷ sè cuèi cïng trong c¬ sè 2. ThËt vËy, gi¶ sö trong c¬ sè 2, n cã d¹ng    1 1 0 1 1 02 2... ... .2n n n nn a a a a a a a a    . NÕu 0 0a  ( 2n m ) th×    1 1 0 1 12 2... ... .2 2n n n nn a a a a a a a m    . NÕu 0 1a  ( 2 1n m  ) th×    1 1 0 1 12 2... ... .2 1 2 1n n n nn a a a a a a a m      . Nh− vËy, trong c¶ hai tr−êng hîp  1 1 2...n nm a a a , hay m chÝnh lμ sè nhËn ®−îc tõ n trong c¬ sè 2 sau khi xãa ch÷ sè 0a . Ta cã 0 2 2 1 0 1 2 2 2 1 1 .2 10...0 10...0 2 10...0 10...0 10...02 k k k k k k k m a m an                                      , trong ®ã 0a lμ ch÷ sè cuèi cïng (ch÷ sè hμng ®¬n vÞ) cña n . V× 0 2 1 10...0 k a   lμ sè thËp ph©n ë hμng thø 1k  trong c¬ sè 2, cßn 2 1 2 10...0 10...0 k k m    lμ sè thËp ph©n nhiÒu nhÊt lμ chØ ®Õn hμng thø k sau dÊu phÈy nªn 2 2 1 0 1 1 2 2 2 1 10...0 10...0 2 10...0 10...0 10...02 k k k k k k k m m an                                     . Tõ ®©y theo gi¶ thiÕt qui n¹p cho m ta cã: 1 2 2 2 2 3 2 2 2 2 2 2 10 1002 2 ... ... 100 10002 2 1 10 ... . 10 100 n nn n m m m                                          (*) 215 MÆt kh¸c, 0 2 01 2 12 102 nn m a             . (**) ThËt vËy, nÕu 2n m th× 0 0a  vμ 2 2 1 2 1 10 2 n m m           , cßn nÕu 2 1n m  th× 0 1a  vμ 2 2 1 2 2 1 10 2 n m m            . LÊy tæng hai vÕ (*) vμ (**) ta ®−îc ®iÒu ph¶i chøng minh: 0 1 2 0 0 2 01 2 3 2 2 2 ... 2 10 2 2 2 n n n m a m m a m a n                             . C¸ch 2. Ta cã thÓ chøng minh trùc tiÕp bμi to¸n nμy nh− sau. Tr−íc tiªn ta cã Bæ ®Ò: Víi mäi sè thùc a ta ®Òu cã    1 2 2 a a a      . Chøng minh: ThËt vËy, gäi  a lμ phÇn lÎ cña a , tøc lμ    a a a  , trong ®ã  0 1a  . Ta xÐt hai tr−êng hîp: 1)   10 2 a  . Khi Êy  1 2 a a     ,    2 2a a , vËy (*) ®óng. 2)  1 1 2 a  . Khi Êy  1 1 2 a a      ,        2 2 2 2 1a a a a    , vËy (*) còng ®óng. Bæ ®Ò ®−îc chøng minh. ¸p dông Bæ ®Ò nμy ta ®−îc: 1 1 2 2 2 2 2 2 2 n n n n nn                                 ; 216 2 2 2 2 1 2 2 2 2 2 n n n n                         ; 2 3 3 2 3 2 1 2 2 2 2 2 n n n n                        ; Céng hai vÕ c¸c ®¼ng thøc trªn ta cã: 0 1 2 1 2 3 2 2 2 ... 2 2 2 n n n n                      . VËy ®¼ng thøc chøng minh xong. Lêi b×nh: C¸ch 2 cã lÏ hay h¬n c¸ch 1, nh−ng chuyÓn sang c¬ sè 2 còng cho ta c¸i nh×n míi h¬n ®èi víi bμi to¸n nμy. Bμi to¸n 6 (Bμi ®Ò nghÞ thi V« ®Þch Quèc tÕ lÇn thø 37, 1996) Gi¶ sö d·y na ®−îc x¸c ®Þnh nh− sau: 1 0a  vμ ( 1) 2 2 ( 1) n n n na a         (*) víi mäi sè nguyªn d−¬ng n . a) X¸c ®Þnh gi¸ trÞ lín nhÊt vμ gi¸ trÞ nhá nhÊt cña na víi 1996n  vμ t×m tÊt c¶ nh÷ng sè 1996n  mμ gi¸ trÞ lín nhÊt hoÆc gi¸ trÞ nhá nhÊt cña na ®¹t ®−îc. b) Cã bao nhiªu sè h¹ng na víi 1996n  mμ 0na  . Gi¶i: Gi¶ sö  1 1 0 2...k kn a a a a lμ biÓu diÔn cña n trong hÖ c¬ sè 2. Ta thÊy r»ng 2 n    cã biÓu diÔn trong hÖ c¬ sè 2 lμ biÓu diÔn cña n sau khi xãa ®i ch÷ sè cuèi cïng 0a , tøc lμ  1 1 2...2 k k n a a a      . ThËt vËy, ta cã 217    1 1 0 1 1 02 2... ... .2k k k kn a a a a a a a a    . NÕu 0 0a  th× n ch½n vμ 2. 2.2 2 n nn       . H¬n n÷a,    1 1 0 1 12 2... ... .2k k k kn a a a a a a a   . Suy ra  1 1 2...2 2 n n n n a a a       . NÕu 0 1a  th× n lÎ vμ 2. 2.2 2 n nn       +1 vμ    1 1 0 1 12 2... ... .2 1k k k kn a a a a a a a    . Suy ra  1 1 21 ...2 2 k k n n a a a       . VËy trong c¶ hai tr−êng hîp ta ®Òu cã  1 1 2...2 k k n a a a      chÝnh lμ sè nhËn ®−îc tõ biÓu diÔn cña n sau khi xãa ®i ch÷ sè cuèi cïng 0a . Ký hiÖu nu lμ tæng sè c¸c cÆp ch÷ sè 00 hoÆc 11 vμ nv lμ tæng sè c¸c cÆp ch÷ sè 10 hoÆc 01 cã trong biÓu diÔn cña n trong c¬ sè 2. Khi Êy ta cã n n na u v  . (**) Tr−íc tiªn ta kiÓm tra c«ng thøc (**) víi mét vμi gi¸ trÞ cña n . Víi 21 1n   th× 1 1 0u v  , do ®ã (**) ®óng v× 1 0a  . NÕu 22 10n   th× 2 0u  ; 2 1v  . Theo c«ng thøc (*) ta cã 2 1 2 21 1a a u v      , tøc lμ c«ng thøc (**) ®óng. NÕu 23 11n   th× 3 1u  ; 3 0v  . Theo c«ng thøc (*) ta cã 3 1 3 31 1a a u v     , tøc lμ c«ng thøc (**) ®óng. NÕu 24 100n   th× 4 1u  ; 4 0v  . Theo c«ng thøc (*) ta cã 4 2 4 41 1a a u v     , tøc lμ c«ng thøc (**) ®óng. NÕu 25 101n   th× 5 0u  ; 5 2v  . Theo c«ng thøc (*) ta cã 5 2 5 51 2a a u v      , tøc lμ c«ng thøc (**) ®óng. NÕu 26 110n   th× 6 1u  ; 6 1v  . Theo c«ng thøc (*) ta cã 6 3 6 61 0a a u v     , tøc lμ c«ng thøc (**) ®óng. 218 NÕu 27 111n   th× 7 2u  ; 7 0v  . Theo c«ng thøc (*) ta cã 7 3 7 71 2a a u v     , tøc lμ c«ng thøc (**) ®óng. Gi¶ sö c«ng thøc (**) ®óng víi mäi 1,2,..., 1p n  . Ta sÏ chøng minh nã ®óng víi p n . XÐt hai tr−êng hîp sau. Tr−êng hîp 1. 0n  (mod 4) hoÆc 3n  (mod 4), tøc lμ  1 2 2... 00n nn a a a hoÆc  1 2 2... 11n nn a a a . Khi Êy theo c«ng thøc (*) vμ gi¶ thiÕt qui n¹p th× 2 2 2 1 1n n n na a u v                     . V× n cã d¹ng  1 2 2... 00n nn a a a (hoÆc  1 2 2... 11n nn a a a ) nªn 2 n    cã d¹ng:  1 2 2... 02 n n n a a a      (hoÆc  1 2 2... 12 n n n a a a      ). Trong c¶ hai tr−êng hîp ta ®Òu cã: 2 1nnu u      ( n cã nhiÒu h¬n 2 n    mét cÆp 00 (hoÆc 11) ë cuèi vμ 2 nnv v     ( n kh«ng cã thªm cÆp 01 hoÆc 10 nμo). VËy ta cã: 2 2 2 1 1 ( 1) 1n n n n nn n na a u v u v u v                           . Tr−êng hîp 2. 1n  (mod 4) hoÆc 2n  (mod 4), tøc lμ  1 2 2... 01n nn a a a hoÆc  1 2 2... 10n nn a a a . Khi Êy theo c«ng thøc (*) vμ c«ng thøc qui n¹p th× 2 2 2 1 1n n n na a u v                     . V× n cã d¹ng  1 2 2... 01n nn a a a (hoÆc  1 2 2... 10n nn a a a ) nªn 2 n    cã d¹ng  1 2 2... 02 n n n a a a      (hoÆc  1 2 2... 12 n n n a a a      ). Trong c¶ hai tr−êng hîp ta ®Òu cã: 2 nnu u     ( n kh«ng cã thªm mét cÆp 00 hoÆc 11 nμo) vμ 2 1nnv v      (n cã thªm cÆp 01 hoÆc 10 ë cuèi). 219 VËy: 2 2 2 1 1 ( 1) 1n n n n nn n na a u v u v u v                           . Trong c¶ hai tr−êng hîp ta ®Òu cã n n na u v  . C«ng thøc (**) chøng minh xong. a) Theo (**), ®Ó na lín nhÊt ta cÇn t×m sè 1996n  sao cho n nu v lμ lín nhÊt. Do 21996 11111001100 lμ sè cã 11 ch÷ sè víi 7 ch÷ sè 1 nªn c¸c sè 1996n  còng cã nhiÒu nhÊt lμ 9 sè 1 (nhiÒu nhÊt lμ thay hai ch÷ sè 0 b»ng hai ch÷ sè 1). Sè 21111111111 1023n   cã 9nu  lín nhÊt vμ 0nv  nhá nhÊt, do ®ã 9n n na u v   còng lín nhÊt. Nh− vËy, víi 1996n  th× gi¸ trÞ lín nhÊt cña na lμ 9. T−¬ng tù, v× 21996 11111001100 lμ sè cã 11 ch÷ sè (10 cÆp ch÷ sè liÒn nhau) nªn 1996n  cã nhiÒu nhÊt lμ 10 cÆp sè 10 hoÆc 01. Sè 210101010101 1365n   cã 0nu  nhá nhÊt vμ 10nv  lín nhÊt, do ®ã na ®¹t gi¸ trÞ nhá nhÊt b»ng –10. b) Gi÷a mäi cÆp ch÷ sè liªp tiÕp cña n trong biÓu diÔn nhÞ ph©n cña nã ta ®Æt mét dÊu chÊm nÕu chóng gièng nhau vμ mét dÊu phÈy nÕu chóng kh¸c nhau. ThÕ th× nu chÝnh lμ sè c¸c dÊu chÊm vμ nv chÝnh lμ sè c¸c dÊu phÈy. VËy, mét d·y cã ®é dμi m c¸c dÊu chÊm phÈy (theo thø tù tõ tr¸i sang ph¶i) sÏ x¸c ®Þnh duy nhÊt mét sè cã ®é dμi 1m  trong c¬ sè 2 (sè cã 1m  ch÷ sè, ch÷ sè ®Çu tiªn bªn tr¸i lμ 1). NÕu 0n n na u v   th× sè c¸c dÊu chÊm vμ sè c¸c dÊu phÈy b»ng nhau, tøc lμ m ph¶i cã sè ch½n, hay 1n m  ph¶i cã sè lÎ sè ch÷ sè trong biÓu diÔn c¬ sè 2. Ta nãi mét d·y gåm c¸c dÊu chÊm vμ dÊu phÈy lμ d·y c©n b»ng nÕu sè dÊu chÊm vμ dÊu phÈy b»ng nhau. Râ rμng mét d·y c©n b»ng cã thÓ t¹o bëi 2 m mC c¸ch nÕu m ch½n vμ kh«ng tån t¹i nÕu m lÎ. Mét sè n tháa m·n ®iÒu kiÖn 0n n na u v   t−¬ng øng mét mét víi mét d·y c©n b»ng c¸c dÊu chÊm vμ phÈy. Do 1996n  mμ 220 21996 11111001100 gåm 11 ch÷ sè nªn n chØ cã thÓ cã 3, 5, 7, 9 hoÆc 11 ch÷ sè (t−¬ng øng, m chØ cã thÓ cã 2, 4, 6, 8 hoÆc 10 dÊu chÊm phÈy). V× 1 0a  nªn cã tÊt c¶ 1 2 3 4 5 2 4 6 8 101 351C C C C C      sè n víi tèi ®a 11 ch÷ sè mμ 0na  . Tuy nhiªn sè n trong c¬ sè 2 cã 11 ch÷ sè cã thÓ lín h¬n 1996, v× vËy ta cßn ph¶i lo¹i bít c¸c sè víi tÝnh chÊt 0n n na u v   trong kho¶ng tõ 1996 ( 211111001100 ) ®Õn 2047=211-1=111111111112, v× chóng lín h¬n 1996 nªn chóng chØ cã thÓ lμ: 211111010010 2002 ; 211111010100 2004 ; 211111010110 2006 ; 211111011010 2010 ; 211111101010 2026 . Nh− vËy, cuèi cïng ta cã tÊt c¶ lμ 351-5=346 sè. Bμi to¸n 7 (V« ®Þch Quèc tÕ lÇn thø 29, 1988) Gi¶ sö :f N N lμ hμm sè tho¶ m·n (1) 1f  , (3) 3f  vμ víi mäi sè nguyªn d−¬ng n th× (2 ) ( )f n f n ; (4 1) 2 (2 1) ( )f n f n f n    ; (4 3) 3 (2 1) 2 ( )f n f n f n    . T×m sè 1988n  mμ ( )f n n . Gi¶i: Mét sè k N bÊt k× chØ cã thÓ cã mét trong bèn d¹ng: 4 2.2k n n  ; 4 1k n  ; 4 2 2(2 1)k n n    vμ 4 3k n  nªn tõ c«ng thøc trong ®Çu bμi cã thÓ thÊy r»ng hμm sè ®· cho ®−îc x¸c ®Þnh mét c¸ch duy nhÊt. Ta sÏ sö dông c¬ sè 2 ®Ó t×m biÓu diÔn hiÓn cña f . Ta cã 2 2(1 ) (1) 1 1f f   ; 2 2(10 ) (2) (1) 1 01f f f    ; 2 2(11 ) (3) 3 11f f   ; 2 2(100 ) (4) (2.2) (2) 1 001f f f f     ; 2 2(101 ) (5) (4.1 1) 2 (3) (1) 2.3 1 5 101f f f f f         ; 2 2(110 ) (6) (2.3) (3) 3 011f f f f     ; 2 2(111 ) (7) (4.1 3) 3 (3) 2 (1) 3.3 2 7 111f f f f f         2 2(1000 ) (8) (4) (2) 1 0001f f f f     ; 221 2 2(1001 ) (9) (4.2 1) 2 (5) (2) 2.5 1 9 1001f f f f f         ; 2 2(1010 ) (10) (5) 0101f f f   . Qui luËt: BiÓu diÔn cña ( )f n trong c¬ sè 2 chÝnh lμ biÓu diÔn cña n b»ng c¸ch viÕt ng−îc l¹i, tøc lμ  1 1 0 2 0 1 1 2(( ... ) ) ...k k k kf a a a a a a a a  . Chøng minh: Gi¶ sö tÝnh chÊt ®óng cho mäi k n . Ta sÏ chøng minh nã ®óng cho n . NÕu n ch½n ( 2n m ) th× theo gi¶ thiÕt ( ) (2 ) ( )f n f m f m  . V× 2n m nªn nÕu m ®−îc biÓu diÔn trong hÖ c¬ sè 2 d−íi d¹ng 1 1 0...k km a a a a th× 1 1 0... 0k kn a a a a . Theo quy n¹p 1 1 0 0 1 1 0 1 1( ) ( ... ) ... 0 ...k k k k k kf m f a a a a a a a a a a a a     . VËy 1 1 0 1 1 0 0 1 1 0 1 1 ( ... 0) ( ) ( ) ( ... ) ... 0 ... . k k k k k k k k f a a a a f n f m f a a a a a a a a a a a a          NÕu 4 1n m  víi 1 1 0...k km a a a a th× 1 1 04 1 ... 01k kn m a a a a   vμ 1 1 02 1 ... 1k km a a a a  . Theo ®Çu bμi vμ gi¶ thiÕt qui n¹p ta cã:   1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 3 2 0 1 1 0 1 1 0 1 1 0 1 1 3 ( ... 01) (4 1) 2 (2 1) ( ) 2.1 ... ( ) 1 ... 0 ( ) 10....0 ... 0 ... 2 2 ... ... 10....0 ... 10 ... . k k k k k k k k k k k k k k k k k k k k k f a a a a f m f m f m a a a a f m a a a a f m a a a a a a a a a a a a a a a a a a a a a a a a                               NÕu 4 3n m  víi 1 1 0...k km a a a a th× 1 1 04 3 ... 11k kn m a a a a   vμ 1 1 02 1 ... 1k km a a a a  . Tõ gi¶ thiÕt cña ®Çu bμi vμ gi¶ thiÕt qui n¹p suy ra:  1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 3 ( ... 11) (4 3) 3 (2 1) 2 ( ) (2 1) 2 (2 1) 2 ( ) 1 ... 1 ... 0 ... 0 1 ... 10...0 11 ... . k k k k k k k k k k k k k f a a a a f m f m f m f m f m f m a a a a a a a a a a a a a a a a a a a a                         VËy qui luËt ®−îc chøng minh. 222 Mét sè trong c¬ sè 2 ®−îc gäi lμ palindromic nÕu nã kh«ng ®æi khi ta ®æi chç c¸c ch÷ sè theo thø tù ng−îc l¹i. Víi mçi k sÏ cã tÊt c¶ 1 22 k    sè palindromic cã ®é dμi k (sè palindromic bËc k ). ThËt vËy, mét sè palindromic hoμn toμn ®−îc x¸c ®Þnh nÕu biÕt tÊt c¶ 1 2 k     ch÷ sè ®Çu tiªn (bªn ph¶i), c¸c ch÷ sè cßn l¹i ®−îc x¸c ®Þnh b»ng c¸ch lÊy ®èi xøng qua sè ®øng gi÷a. V× ch÷ sè ë vÞ trÝ ®Çu tiªn bªn ph¶i b¾t buéc ph¶i lμ 1, nªn chØ cßn l¹i 1 11 2 2 k k            vÞ trÝ tïy chän lμ ch÷ sè 0 hoÆc ch÷ sè 1. Cã 1 2 1 2 2 2 ... 2 2 k k             kh¶ n¨ng chän, tøc lμ cã tÊt c¶ 1 22 k    sè palindromic bËc k . Tõ qui luËt trªn suy ra nghiÖm cña ph−¬ng tr×nh ( )f n n víi 21988 11111001110n   chÝnh lμ c¸c sè palindromic víi tèi ®a 10 ch÷ sè vμ nh÷ng sè cã 11 ch÷ sè nh−ng nhá h¬n 1988n  . V× cã mét sè víi 1 ch÷ sè (sè 1=12) vμ mét sè víi 2 ch÷ sè trong c¬ sè 2 (sè 3=112) tháa m·n ph−¬ng tr×nh ( )f n n nªn cã tÊt c¶ 3 1 4 1 9 1 10 1 2 2 2 21 1 2 2 ... 2 2 2(1 2 ... 16) 62                                    sè cã tèi ®a 10 ch÷ sè trong c¬ sè 2, tøc lμ cã tÊt c¶ 62 sè trong kho¶ng 0 1023n  tho¶ m·n ph−¬ng tr×nh ( )f n n . Cã tÊt c¶ 11 1 22 32      sè trong kho¶ng 1024 2047n  (cã 11 ch÷ sè) lμ palindromic. Trong c¸c sè ®ã cã hai sè 111111111112=2047 vμ 111110111112=2015 v−ît qu¸ 1988. VËy cã tÊt c¶ 32-2=30 sè trong kho¶ng 1024 1988n  tho¶ m·n ph−¬ng tr×nh ( )f n n . Cuèi cïng, ph−¬ng tr×nh ( )f n n cã tÊt c¶ 62+30=92 nghiÖm. Bμi to¸n 8 (§Ò dù tuyÓn V« ®Þch Quèc tÕ lÇn thø 35, 1995) 223 Víi mçi sè tù nhiªn k , ký hiÖu ( )p k lμ sè nguyªn tè nhá nhÊt kh«ng chia hÕt k . NÕu ( ) 2p k  ta ký hiÖu ( )q k lμ tÝch cña tÊt c¶ c¸c sè nguyªn tè nhá h¬n ( )p k , nÕu ( ) 2p k  ®Æt ( ) 1q k  . XÐt d·y 0 1x  , 1 ( )( ) n n n n x p xx q x  , n =0,1,2, X¸c ®Þnh tÊt c¶ c¸c sè n sao cho 1995nx  . Gi¶i: Tõ ®Þnh nghÜa cña ( )p k vμ ( )q k , ta thÊy ( )q k lu«n chia hÕt k , do ®ã 1 ( ) ( ) n n n n x p xx q x  lu«n lμ mét sè nguyªn d−¬ng. Ta thÊy nx kh«ng ph¶i lμ sè chÝnh ph−¬ng víi mäi n =1,2, ThËt vËy, tr−íc tiªn ta kiÓm tra víi mét vμi gi¸ trÞ ®Çu cña n . Víi 0n  : 0 1x  ; 0( ) 2p x  , 0( ) 1q x  . VËy 0 01 0 ( ) 2 ( ) x p xx q x   . Víi 1n  : 1 2x  ; 1( ) 3p x  ; 1( ) 2q x  . VËy 1 12 1 ( ) 3 ( ) x p xx q x   . Víi 2n  : 2 3x  ; 2( ) 2p x  ; 2( ) 1q x  , 2 23 2 ( ) 6 ( ) x p xx q x   . Víi 3n  : 3 6x  ; 3( ) 5p x  ; 3( ) 2.3q x  ; 3 34 3 ( ) 5 ( ) x p xx q x   . Nh− vËy, mäi nx , 0,1, 2, 3n  ®Òu kh«ng lμ sè chÝnh ph−¬ng. Ta chøng minh r»ng, nx kh«ng ph¶i lμ sè chÝnh ph−¬ng víi mäi 0n  . ThËt vËy, gi¶ sö ph¶n chøng nÕu 1nx  lμ sè chÝnh ph−¬ng, tøc lμ 21nx t  . Ph©n tÝch t thμnh thõa sè nguyªn tè ta ®−îc 1... kt t t ( it , jt cã thÓ b»ng nhau). Khi Êy 12 2 21 2 ( ) ... ( ) k n n n n x p xx t t t q x   , hay 1 2 2 2 2( ) ... ( )kn n nx p x t t t q x , nh−ng ( )np x (lμ sè nguyªn tè) kh«ng chia hÕt cho ( )nq x nªn ph¶i b»ng mét sè 0it víi  0 1,...,i k nμo ®ã. Chia hai vÕ cho 0 ( )n ip x t ta cßn l¹i 1 0 0 02 2 2 2 22 1 1... ... ( )kn i i i nx t t t t t t q x  , tøc lμ nx còng ph¶i chia hÕt cho 0i t = ( )np x . §iÒu nμy v« lÝ v× nx kh«ng chia hÕt 224 cho ( )np x . VËy víi mäi 0n  th× nx kh«ng ph¶i lμ sè chÝnh ph−¬ng . Ta sÏ chøng minh theo quy n¹p r»ng, nÕu 0 1 22, 3, 5,...p p p   lμ d·y tÊt c¶ c¸c sè nguyªn tè ®−îc x¾p xÕp theo chiÒu t¨ng vμ n cã biÓu diÔn trong c¬ sè 2 lμ  1 1 0 2...m mn c c c c th× 0 1 20 1 2 ... mc cc cn mx p p p p . Víi 21 1n   : 0 1c  , 0 2p  ; 01 02 cx p  . Víi 22 10n   : 0 0c  , 1 1c  ; 0 2p  , 1 3p  ; 0 12 0 13 c cx p p  . Víi 23 11n   : 0 1c  , 1 1c  ; 0 13 0 16 2.3 c cx p p   . Víi 24 100n   : 0 0c  , 1 0c  , 2 1c  ; 0 1 24 0 1 25 c c cx p p p  . Gi¶ sö ®iÒu nμy ®óng víi mäi k n . Ta sÏ chøng minh nã ®óng víi 1k n  . Gi¶ sö theo qui n¹p  1 1 0 2...m mn c c c c th× 0 1 20 1 2 ... mc cc cn mx p p p p . NÕu 0 0c  th× n lμ ch½n vμ cã d¹ng  1 1 2... 0m mn c c c . V× khi Êy 0 1 2 1 2 0 1 2 1 2... ...m m c c cc c c c n m mx p p p p p p p  lμ tÝch cña c¸c sè nguyªn tè lÎ nªn lμ ph¶i mét sè lÎ, do ®ã ( ) 2np x  vμ ( ) 1nq x  . Suy ra 1 2 1 21 1 1 2 0 1 2 ( ) 2 ... ... ( ) m mc cc c c cn n n m m n x p xx p p p p p p p q x    . Nh−ng  1 1 21 ... 1m mn c c c  nªn kh¼ng ®Þnh qui n¹p lμ ®óng. NÕu 0 1c  th× n lμ lÎ. Gi¶ sö  1 1 2... 01...1m m kn c c c  víi k m , tøc lμ 0 1 2 0 1 2 ... m c cc c n mx p p p p chia hÕt cho ip , 0, 1, 2,..., 1i k  vμ kh«ng chia hÕt cho kp , suy ra ( )n kp x p vμ 0 1( ) ...n kq x p p  , do ®ã 1 2 1 20 0 1 1 1 2 0 1 1 2 ( ) ... ... ... ( ) k k m k k m k c c c c c cn n n k k k m k k k m n x p xx p p p p p p p p p p q x            . Nh−ng  1 21 ... 10...00m m kn c c c  nªn kh¼ng ®Þnh qui n¹p lμ ®óng. Tr−êng hîp  211.....11n  th× 0 1 20 1 2 ... mc cc cn mx p p p p chia hÕt cho ip , 0, 1, 2,...,i m vμ kh«ng chia hÕt cho 1mp  , suy ra 1( )n mp x p  vμ 0( ) ...n mq x p p , do ®ã 1 0 0 10 1 1 0 0 ( ) ... ( ) ... ( ) ... m n n m n n m m n m x p x p p p xx p p p p q x p p       . 225 Nh−ng khi Êy  1 2 10...0 m n       nªn kh¼ng ®Þnh qui n¹p còng ®óng. VËy kh¼ng ®Þnh qui n¹p chøng minh xong. Tõ kh¼ng ®Þnh trªn, do 0 1 1 1 0 0 0 11995 3.5.7.19 2 .3 .5 .7 .11 .13 .17 .19nx    nªn 2 1010001110 142n   . §¸p sè: 142n  . Bμi to¸n 9 (V« ®Þch Ba Lan, 1995) Víi mçi sè tù nhiªn k , ký hiÖu ( )p k lμ sè nguyªn tè nhá nhÊt kh«ng chia hÕt k . NÕu ( ) 2p k  ta ký hiÖu ( )q k lμ tÝch cña tÊt c¶ c¸c sè nguyªn tè nhá h¬n ( )p k , ng−îc l¹i ®Æt ( ) 1q k  . XÐt d·y 0 1x  , 1 ( )( ) n n n n x p xx q x  , n =0,1,2, X¸c ®Þnh tÊt c¶ c¸c sè n sao cho 111111nx  . Gi¶i: Theo bμi trªn (Bμi to¸n 8) ta cã: 0 1 0 1 1 1 0 0 0 0 0 1 1 3 4 5 11 111111 3.7.11.13.37 2 .3 .5 .7 .11 .13 .17 .19 .23 .29 .31 .37 . . . . . nx p p p p p     VËy 111111nx  khi vμ chØ khi 11 5 4 3 1 2100000111010 2 2 2 2 2 2106n        . §¸p sè: 2106n  . Bμi to¸n 10 (V« ®Þch Quèc gia Ba Lan, 1997) Gi¶ sö d·y na ®−îc x¸c ®Þnh nh− sau: 1 0a  vμ ( 1) 2 2 ( 1) n n n na a         (*) víi mäi sè nguyªn d−¬ng n . Víi mçi sè nguyªn 0k  , h·y t×m sè tÊt c¶ c¸c sè n tháa m·n 12 2k kn   vμ 0na  . 226 Gi¶i: Theo Bμi to¸n 5 ta cã n n na u v  , trong ®ã nu lμ tæng sè c¸c cÆp 00 vμ 11, cßn nv lμ tæng sè c¸c cÆp 01 vμ 10. B©y giê cho tr−íc sè nguyªn 0k  , ta cÇn t×m c¸c sè n sao cho 12 2k kn   vμ 0na  , tøc lμ n nu v hay tæng c¸c cÆp 00 hoÆc 11 b»ng tæng c¸c cÆp 10 hoÆc 10 trong biÓu diÔn cña n . V× 12 2k kn   nªn n cã 1k  ch÷ sè trong biÓu diÔn c¬ sè 2. Gi÷a mäi cÆp ch÷ sè liªp tiÕp cña n trong biÓu diÔn nhÞ ph©n cña nã (cã ®é dμi lμ 1k  ) ta ®Æt mét dÊu chÊm nÕu chóng gièng nhau vμ mét dÊu phÈy nÕu chóng kh¸c nhau. Nh− vËy, sè n sÏ t−¬ng øng víi mét d·y k dÊu chÊm phÈy. Mét sè n tháa m·n ®iÒu kiÖn 0n n na u v   t−¬ng øng mét mét víi mét d·y c©n b»ng c¸c dÊu chÊm vμ phÈy (sè dÊu chÊm vμ dÊu phÈy b»ng nhau). Mét d·y c©n b»ng cã thÓ t¹o bëi 2 k kC c¸ch nÕu k ch½n vμ kh«ng tån t¹i nÕu k lÎ (xem lêi gi¶i Bμi to¸n 5). Nh− vËy, nÕu k ch½n th× cã tÊt c¶ 2 k kC sè n vμ kh«ng tån t¹i n nμo nÕu k lÎ tháa m·n hai ®iÒu kiÖn 12 2k kn   vμ 0na  . Bμi to¸n 11 (Thi mïa ®«ng Bungaria, 2001) Cho nA lμ sè tÊt c¶ c¸c sè nhÞ ph©n cã ®é dμi n vμ kh«ng d·y nμo chøa bèn phÇn tö liªn tiÕp b»ng 0101. Hái 2001A lμ sè ch½n hay lÎ? Gi¶i: KÝ hiÖu nijka lμ sè nhÞ ph©n cã ®é dμi n kh«ng chøa bèn ph©n tö liªn tiÕp 0101 mμ ba sè cuèi cïng lμ ijk víi  , , 0;1i j k . Cã thÓ thÊy r»ng, 1101 110 n na a  vμ 1 1 0 ij n n n ijk ija a a    khi 101ijk  . Céng tÊt c¶ c¸c ®¼ng thøc trªn khi , ,i j k thay ®æi, ta ®−îc 1 0102 n n nA A a   . Suy ra 1 010 (mod 2) n nA a  . Mμ 227                     1 1 2 2 2 010 001 101 000 100 110 3 3 3 3 3 3 000 100 010 110 011 111 4 4 4 4 4 4 000 100 010 110 001 101 4 4 4 4 4 4 011 111 001 101 011 111 4 000 1 n n n n n n n n n n n n n n n n n n n n n n n n n a a a a a a a a a a a a a a a a a a a a a a a a a a                                                        4 4 4 4 4 4 400 010 110 001 101 011 1112 2n n n n n n na a a a a a            nªn 4 4 4 4 010 000 100 010 110 n n n n na a a a a       . TiÕp tôc:         4 4 4 4 010 000 100 010 110 5 5 5 5 5 5 5 5 000 100 010 110 001 101 011 111 5 n n n n n n n n n n n n n n a a a a a a a a a a a a a A                           VËy cuèi cïng 1 010 5 (mod 2) n n nA a A   . §Æt 1 6n k m   ta ®−îc 6 ( 6 1) 5 6( 1) ... (mod 2)k m k m k m kA A A A         . Víi 3k  ta cã 2001 3 8 0(mod 2)A A   hay 2001A lμ sè ch½n. Bμi to¸n 12 (§Ò dù tuyÓn V« ®Þch Quèc tÕ 1999) Mét nhμ sinh vËt häc quan s¸t mét con th¹ch sïng ®ang b¾t ruåi vμ nã nghØ ng¬i sau mçi lÇn b¾t ®−îc mét con ruåi. Nhμ sinh vËt häc nμy nhËn thÊy r»ng: (i) Con ruåi ®Çu tiªn bÞ b¾t sau thêi gian nghØ mét phót; (ii) Thêi gian nghØ tr−íc khi bÞ b¾t con ruåi thø 2m b»ng thêi gian nghØ tr−íc khi b¾t con ruåi thø m vμ kÐm mét phót so víi thêi gian nghØ tr−íc khi b¾t con ruåi thø 2 1m  ; (iii) Khi th¹ch sïng hÕt nghØ, nã b¾t ruåi ngay lËp tøc. Hái: a) Cã bao nhiªu con ruåi bÞ b¾t tr−íc thêi gian nghØ lÇn ®Çu tiªn lμ 9 phót? b) Sau bao nhiªu phót th× th¹ch sïng b¾t ®−îc con ruåi thø 98? 228 c) Cã bao nhiªu con ruåi bÞ th¹ch sïng b¾t sau 1999 phót tr«i qua? Gi¶i: KÝ hiÖu ( )r m lμ ®é dμi thêi gian (sè phót) con th¹ch sïng nghØ ng¬i tr−íc khi b¾t con ruåi thø m (tøc lμ thêi gian tõ khi b¾t con ruåi thø 1m  ®Õn khi b¾t con ruåi thø m ). Tõ gi¶ thiÕt ta cã: (1) 1;r  (2 ) ( )r m r m ; (2 1) ( ) 1r m r m   . (*) Nh− vËy, theo Bμi to¸n 3, ( )r m chÝnh lμ sè ch÷ sè 1 trong biÓu diÔn nhÞ ph©n cña m . KÝ hiÖu ( )t m lμ thêi ®iÓm ngay tr−íc lÇn b¾t thø m (tøc lμ tæng sè thêi gian tõ ®Çu ®Õn khi b¾t con ruåi thø m ) vμ ( )f n lμ sè ruåi bÞ b¾t sau n phót tr«i qua. Khi Êy theo bμi ra ta cã víi mäi m : 1 ( ) ( ) m i t m r i   vμ ( ( ))f t m m . (**) Tr−íc tiªn chóng ta chøng minh mét sè c«ng thøc truy håi sau: 1) (2 1) 2 ( ) 1t m t m m    . (1) ThËt vËy, tõ c¸c c«ng thøc (*) vμ (**) suy ra: 2 1 1 0 1 1 1 1 (2 1) ( ) (2 1) (2 ) (1) ( ( ) 1) ( ) 2 ( ) 1 2 ( ) 1. m m m i i i m m m i i i t m r i r i r i r r i r i r i m t m m                             VËy (1) ®−îc chøng minh. 2) (2 ) 2 ( ) ( )t m t m m r m   ; (2) Còng tõ c¸c c«ng thøc (*) vμ (**) ta cã: 2 1 2 1 1 (2 1) ( ) ( ) (2 1) (2 ) ( ) 1 m m i i t m r i r i r m t m r m             . Tõ c«ng thøc nμy vμ c«ng thøc (1) suy ra: (2 ) (2 1) ( ) 1 (2 ( ) 1) ( ) 1 2 ( ) ( ). t m t m r m t m m r m t m m r m             229 C«ng thøc (2) ®−îc chøng minh. 3) (2 ) ( )pr m r m ; (3a) (2 1)qr q  . (3b) ThËt vËy, ¸p dông c«ng thøc (*) ta ®−îc: 1 1 2(2 ) (2.2 ) (2 ) (2 ) ... ( )p p p pr m r m r m r m r m       vμ 1 1 2 (2 1) (2.(2 1) 1) (2 1) 1 ( (2 1) 1) 1 ... (1) ( 1) . q q q q r r r r r q q                    C«ng thøc (3) ®−îc chøng minh. 4) 1(2 ) 2 ( ) 2 (2 1) ( )p p p pt m t m pm r m    . (4) Víi 1p  c«ng thøc (4) chÝnh lμ c«ng thøc (2) ®· ®−îc chøng minh. Víi 2p  , tõ c«ng thøc (2) vμ c«ng thøc (*) ta cã: 2 2 2 1 2 (2 ) (2.2 ) 2 (2 ) 2 (2 ) 2(2 ( ) ( )) 2 ( ) 4 ( ) 4 3 ( ) 2 ( ) 2 2 (2 1) ( ). t m t m t m m r m t m m r m m r m t m m r m t m m r m                 Ta sÏ chøng minh c«ng thøc (4) nhê c«ng thøc (2), (3) vμ qui n¹p theo p nh− sau: 1 1 1 1 (2 ) (2.2 ) 2 (2 ) 2 (2 ) 2(2 ( ) 2 (2 1) ( )) 2 ( ) 2 ( ) ( 1) 2 (2 1) ( ). p p p p p p p p p p p p t m t m t m m r m t m pm r m m r m t m p m r m                    VËy c«ng thøc (4) ®−îc chøng minh. Tõ ®©y ta cã c¸c hÖ qu¶: 5) 1(2 1) .2p pt p   ; (5a) 1(2 ) .2 1p pt p   . (5b) Liªn tiÕp ¸p dông c«ng thøc (1) ta ®−îc: 230 1 1 1 1 1 2 2 1 2 2 1 1 1 1 1 1 (2 1) (2(2 1) 1) 2 (2 1) (2 1) 1 2 (2 1) 2 2(2 (2 1) 2 ) 2 2 (2 1) 2.2 ... 2 (1) ( 1)2 2 ( 1)2 .2 . p p p p p p p p p p p p p p p p t t t t t t t p p p                                           VËy c«ng thøc (5a) ®−îc chøng minh. ¸p dông c«ng thøc (4) cho 1m  víi chó ý r»ng (1) (1) 1t r  ta ®−îc: 1 1(2 ) 2 (1) .1.2 (2 1) (1) .2 1.p p p p pt t p r p       VËy c«ng thøc (5b) ®−îc chøng minh. 6) 1 1(2 .(2 1)) ( )2 2 .2p q p q p pt p q p q q        . (6) ¸p dông c«ng thøc (4) cho 2 1qm   , c«ng thøc (3b) vμ (5a) ta ®−îc: 1 1 1 1 1 (2 .(2 1)) 2 (2 1) .(2 1).2 (2 1) (2 1) 2 .2 .(2 1).2 (2 1). ( )2 2 .2 . p q p q q p p q p q q p p p q p p t t p r q p q p q p q q                         VËy c«ng thøc (6) ®−îc chøng minh. B©y giê ta ®i gi¶i quyÕt bμi to¸n. a) Sè ruåi bÞ b¾t sau lÇn nghØ ®Çu tiªn mÊt 9 phót chÝnh lμ thêi gian ®Çu tiªn mμ kho¶ng c¸ch nghØ gi÷a lóc b¾t con ruåi thø m vμ thø 1m  lμ 9 phót, còng chÝnh lμ sè m sao cho ( 1) 9r m   . V× ( )r m chÝnh lμ sè ch÷ sè 1 trong biÓu diÔn nhÞ ph©n cña m , nªn ( 1) 9r m   ph¶i cã 9 ch÷ sè 1, mμ sè bÐ nhÊt cã 9 ch÷ sè 1 lμ 10 2111111111 2 1 511   nªn m =510. b) Sö dông c¸c c«ng thøc (1), (2) vμ (6) ta ®−îc: (98) 2 (49) 49 (49)t t r   ; (49) 2 (24) 24 1t t   ; 3 3 2 4 2 3(24) (2 .3) (2 .(2 1)) 5.2 3.2 2.2 2 54t t t        . Suy ra (49) 2 (24) 24 1 133t t    . V× 2(49) (110001 ) 3r r  nªn 231 (98) 2 (49) 49 (49) 312t t r    (con ruåi). c) V× ( )t m lμ thêi ®iÓm b¾t con ruåi thø m nªn ( ( ))f t m m . Do ®ã ( )f n m khi vμ chØ khi  ( ); ( 1)n t m t m  , vËy ®Ó t×m ®−îc (1999)f ta ph¶i t×m 0m sao cho 0 0( ) 1999 ( 1)t m t m   . V× ( )t m lμ mét hμm t¨ng nªn ta cã thÓ thö mét sè gi¸ trÞ cña m råi thu hÑp dÇn kho¶ng chøa 0m ®Ó cuèi cïng ®−îc 0m . ¸p dông c«ng thøc (5b) cho 8p  vμ 9p  ta ®−îc 8 7 8 9(2 ) 8.2 1 1024 1999 2305 9.2 1 (2 )t t        . VËy 8 902 2m  . Ta dïng ph−¬ng ph¸p chia ®«i ®Ó thu hÑp ®o¹n chøa 0m nh− sau. KÝ hiÖu 8 9 7 7 2 1 2 2 2 .3 2 .(2 1) 2 m     . TÝnh 1( )t m theo c«ng thøc (6): 7 2 8 6 7 1( ) (2 .(2 1)) 9.2 7.2 2.2 2 1602t m t       . VËy 7 902 .3 2m  . KÝ hiÖu 7 9 6 6 3 2 2 .3 2 2 .7 2 .(2 1) 2 m     . TÝnh 2( )t m theo c«ng thøc (6): 6 3 8 5 6 2( ) (2 .(2 1)) 9.2 6.2 3.2 3 1923t m t       . VËy 6 90448 2 .7 2 512m    . KÝ hiÖu 6 9 5 5 4 3 2 .7 2 2 .15 2 .(2 1) 2 m     . TÝnh 3( )t m theo c«ng thøc (6): 5 4 8 4 5 3( ) (2 .(2 1)) 9.2 5.2 4.2 4 2100t m t       . VËy 6 50448 2 .7 2 .15 480m    . KÝ hiÖu 6 5 4 4 2 .7 2 .15 2 .29 464 2 m    . Tõ (3b) ta cã 3(7) (2 1) 3r r   (hoÆc (7) (111) 3r r  ). 232 Tõ c«ng thøc (5a) suy ra 3 3 1(7) (2 1) 3.2 12t t     . TÝnh 4( )t m theo c«ng thøc (4) víi chó ý lμ (7) 12t  vμ (7) 3r  : 4 4 3 4 4 4 ( ) (2 .29) 2 (29) 4.29.2 (2 1) (29) 2 (2 (14) 15) 928 15( (14) 1) 32(2 (7) 7 (7)) 1153 15 (7) 64 (7) 1377 47 (7) 64.12 1377 47.3 2004. t m t t r t r t r r t r                       VËy 6 4 0448 2 .7 2 .29 464m    . KÝ hiÖu 6 4 3 5 2 .7 2 .29 2 .57 456 2 m    . Tõ c¸c c«ng thøc (1) vμ (2), do (7) 12t  vμ (7) 3r  ta cã: (57) 2 (28) 29 2(2 (14) 14 (14)) 29 4(2 (7) 7 (7)) 57 2 (7) 8 (7) 85 6 (7) 8.12 85 6.3 163. t t t r t r r t r                   Theo c«ng thøc (*) víi chó ý lμ (7) 3r  ta cã: (57) (28) 1 (14) 1 (7) 1 4r r r r       . VËy 3 3 3 1 3 5( ) (2 .57) 2 (57) 3.57.2 (2 1) (57) 8.163 684 7.4 1960. t m t t r         Do ®ã 3 40456 2 .57 2 .29 464m    . KÝ hiÖu 4 3 2 6 2 .29 2 .57 2 .115 460 2 m    . V× (115) 2 (57) 58 2.163 58 384t t     vμ (115) (57) 1 4 1 5r r     nªn 2 2 2 6( ) (2 .115) 2 (115) 2.115.2 (2 1) (115) 4.384 460 3.5 1981. t m t t r         VËy 2 40460 2 .115 2 .29 464m    . KÝ hiÖu 2 4 7 2 .115 2 .29 2.231 462 2 m    . TÝnh 7( )t m theo c«ng thøc (4): 233 7( ) (2.231) 2 (231) 231 (231) 2(2 (115) 116) 231 ( (115) 1) 4 (115) 462 (115) 4.384 462 5 1993. t m t t r t r t r                 VËy 40462 2.231 2 .29 464m    . KÝ hiÖu 8 462 464 463 2 m   . TÝnh 8( )t m : 8( ) 2 (231) 232 2(2 (115) 116) 232 2000t m t t      . Nh− vËy, ta cã (462) 1993t  vμ (463) 2000t  . VËy chØ cã duy nhÊt 0 462m  tho¶ m·n 0 0( ) 1999 ( 1)t m t m   , hay (1999) 462f  . Lêi b×nh: Ph−¬ng ph¸p chia ®«i tuy h¬i dμi, nh−ng kh«ng ®ßi hái lËp luËn s¸ng t¹o ®éc ®¸o, thùc hiÖn tÝnh to¸n kh«ng khã, nhÊt lμ kÕt hîp dïng m¸y tÝnh. §¸p sè: 462 Bμi to¸n 13 (Thi mïa ®«ng Bungaria, 2001) Ivan vμ Peter thay nhau viÕt c¸c ch÷ sè 0 hoÆc 1 (mçi lÇn mét ch÷ sè) cho ®Õn khi mçi ng−êi viÕt ®−îc 2001 ch÷ sè. Nh− vËy, ta sÏ nhËn ®−îc mét d·y gåm 4002 ch÷ sè 0 hoÆc 1. Coi ®©y lμ biÓu diÔn nhÞ ph©n cña mét sè. Peter lμ ng−êi th¾ng cuéc nÕu sè nhËn ®−îc kh«ng viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng. Chøng minh r»ng Peter (®i sau) cã chiÕn l−îc ®¶m b¶o anh ta th¾ng cuéc. Gi¶i: Tr−íc tiªn ta chøng minh r»ng nÕu biÓu diÔn nhÞ ph©n cña mét sè cã tËn cïng b»ng 11 hoÆc mét sè ch½n c¸c ch÷ sè 0 th× sè ®ã kh«ng thÓ lμ tæng cña hai sè chÝnh ph−¬ng. ThËt vËy, mét sè A cã biÓu diÔn nhÞ ph©n cã tËn cïng b»ng 11 th× sè ®ã cã d¹ng 1 3 2 2 1 3 2 2 2... 11 ... 00 11 4 3m m m mA a a a a a a a a s      . NÕu A viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng th× tån t¹i hai sè p vμ q sao cho 2 2 4 3A p q s    . Do A lμ sè lÎ nªn b¾t buéc mét trong hai sè p vμ q lμ lÎ, cßn sè kia lμ ch½n, nghÜa lμ 12p p vμ 12 1q q  . Suy ra 234 2 2 2 2 2 2 1 1 1 1 14 (2 1) 4( ) 1p q p q p q q        , kh«ng d¹ng 4 3s  , v« lÝ. VËy 4 3A s  kh«ng thÓ viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng. H¬n n÷a, ta chøng minh r»ng nÕu biÓu diÔn nhÞ ph©n cña mét sè cã tËn cïng lμ sè 11 vμ tiÕp theo lμ mét sè ch½n c¸c ch÷ sè 0 th× sè ®ã còng kh«ng thÓ lμ tæng cña hai sè chÝnh ph−¬ng. ThËt vËy, sè ®ã cã d¹ng   1 3 2 1 3 2 2 2 2 ... 110...0 4 ... 11 4 (4 3)k km m m m k A a a a a a a a a s         . Gi¶ sö A viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng, tøc lμ tån t¹i hai sè p vμ q sao cho 2 2 4 (4 3)kA p q s    . NÕu 0k  th× v« lÝ do chøng minh trªn. NÕu 0k  th× 2 2A p q  ch½n vμ chia hÕt cho 4. §iÒu nμy chØ x¶y ra khi vμ chØ khi p vμ q cïng ch½n (nÕu p vμ q cïng lÎ th× ta cã  2 2 2(mod 4)p q  . NghÜa lμ 12p p vμ 12q q . Suy ra 2 2 11 1 4 (4 3)kp q s   . LËp luËn t−¬ng tù, cuèi cïng ta ®i ®Õn 2 2 4 3n np q s   . V« lÝ. B©y giê ta x©y dùng chiÕn l−îc ®Ó Peter (®i sau) th¾ng cuéc nh− sau: NÕu mét trong c¸c ch÷ sè mμ Ivan viÕt lμ 1 th× sau mçi lÇn Ivan viÕt xong, Peter sÏ lÆp l¹i ®óng ch÷ sè mμ Ivan ®· viÕt. Khi Êy sè nhËn ®−îc sÏ lμ mét sè trong c¬ sè 2 cã tËn cïng lμ 11 vμ mét sè ch½n c¸c ch÷ sè 0, tøc lμ sè d¹ng 1 3 2 2 2 ... 110...0 4 (4 3)km m k A a a a a s       , sè nμy kh«ng thÓ viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng. NÕu Ivan lu«n chØ viÕt ch÷ sè 0 th× Peter sÏ viÕt ba ch÷ sè ®Çu lμ 1, c¸c ch÷ sè cßn l¹i lμ 0. Sau 2001 b−íc ®i ta ®−îc sè    1998 19982 2 1998 2 0101010...0 010101 4 21 4A          . LÝ luËn t−¬ng tù nh− tr−êng hîp 4 (4 3)kA s  , v× 21 kh«ng thÓ viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng nªn 235 199821 4A   còng kh«ng thÓ viÕt ®−îc d−íi d¹ng tæng cña hai sè chÝnh ph−¬ng. VËy Peter bao giê còng th¾ng. Bμi to¸n 14 (Dù tuyÓn thi V« ®Þch Quèc tÕ lÇn thø 41, 2000) Hμm sè :F N N x¸c ®Þnh trªn tËp c¸c sè nguyªn kh«ng ©m tháa m·n c¸c ®iÒu kiÖn sau víi mäi 0n  : (i) (4 ) (2 ) ( )F n F n F n  ; (ii) (4 2) (4 ) 1F n F n   ; (iii) (2 1) (2 ) 1F n F n   . Chøng minh r»ng víi mçi sè nguyªn d−¬ng m , sè c¸c sè nguyªn n víi 0 2mn  vμ (4 ) (3 )F n F n b»ng 1(2 )mF  . Gi¶i: Do (i) ta cã (4.0) (2.0) (0)F F F  . Suy ra (0) 0F  . T−¬ng tù, tõ (ii) suy ra (2) (4.0 2) (4.0) 1 1F F F     . Tõ (iii) ta cã: (3) (2 1) (2) 1 2F F F     . Ta thÊy ( )F n x¸c ®Þnh mét c¸ch duy nhÊt tõ ba ®iÒu kiÖn cña ®Çu bμi. TiÕp tôc tÝnh ta cã b¶ng gi¸ trÞ cña ( )F n d−íi ®©y. n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ( )F n 0 1 1 2 2 3 3 4 3 4 4 5 5 6 6 7 5 Quan s¸t b¶ng trªn ta cã NhËn xÐt 1: 1(2 )r rF u  , trong ®ã ru lμ sè h¹ng thø r cña d·y Fibonacci ( 0 0u  , 1 1u  , 1 1n n nu u u   , 1n  ). ThËt vËy, víi 0r  ta cã 0 1(2 ) (1) 1F F u   ; Víi 1r  ta cã 1 2 1 1(2 ) (2) 1F F u u     ; Víi 2r  ta cã 2 3 2 1(2 ) (4) 2F F u u     ; Víi 3r  ta cã 3 4 3 1(2 ) (8) 3F F u u     ; Víi 4r  ta cã 4 5 4 1(2 ) (16) 5F F u u     . 236 Gi¶ sö kh¼ng ®Þnh trªn ®óng víi mäi 1 k r  . Ta sÏ chøng minh nã ®óng cho 1r  . §iÒu nμy dÔ dμng suy ra tõ (i), tõ gi¶ thiÕt qui n¹p vμ tõ ®Þnh nghÜa cña d·y Fibonacci: 1 1 1 1 1 ( 1) 1 2(2 ) (4.2 ) (2.2 ) (2 ) r r r r r r rF F F F u u u              . Quan s¸t b¶ng gi¸ trÞ cña ( )F n tÝnh theo n vμ nu d−íi ®©y n nu  2n ( )F n 1 0 1( ) ...k kF n a u a u   0 0 20 0 1(0) 0. 0F u  1 1 12 1 1(1) 1. 1F u  2 1 102 1 2 1(2) 1. 0 1F u u   3 2 112 2 2 1(3) 1. 1 2F u u   4 3 1002 2 3 2 1(4) 1. 0. 0. 2F u u u    5 5 1012 3 3 2 1(5) 1. 0. 1. 3F u u u    6 8 1102 3 3 2 1(6) 1. 1. 0. 3F u u u    7 13 1112 4 3 2 1(7) 1. 1. 1. 4F u u u    8 21 10002 3 4 3 2 1(8) 1. 0. 0. 0. 3F u u u u     9 34 10012 4 4 3 2 1(9) 1. 0. 0. 1. 4F u u u u     10 55 10102 4 4 3 2 1(10) 1. 0. 1. 0. 4F u u u u     11 89 10112 5 4 3 2 1(11) 1. 0. 1. 1. 5F u u u u     12 144 11002 5 4 3 2 1(12) 1. 1. 0. 0. 5F u u u u     13 233 11012 6 4 3 2 1(13) 1. 1. 0. 1. 6F u u u u     14 377 11102 6 4 3 2 1(14) 1. 1. 1. 0. 6F u u u u     15 610 11112 7 4 3 2 1(15) 1. 1. 1. 1. 7F u u u u     16 987 100002 5 5 4 3 2 1(16) 1. 0. 0. 0. 0. 5F u u u u u      ta thÊy ( )F n ®−îc biÓu diÔn d−íi d¹ng tæng cña c¸c sè h¹ng cña d·y Fibonacci. H¬n n÷a, ta cã nhËn xÐt tæng qu¸t sau. NhËn xÐt 2: NÕu n cã biÓu diÔn c¬ sè 2 lμ  0 2...kn a a th× 1 0 1( ) ...k kF n a u a u   . (*) Chøng minh: Ta chøng minh r»ng ( )F n ®−îc x¸c ®Þnh theo c«ng thøc (*) sÏ tháa m·n c¶ ba ®iÒu kiÖn (i), (ii), (iii) víi mäi 0n  . 237 ThËt vËy, nÕu  0 2...kn a a th×  0 24 ... 00kn a a ;  0 24 2 ... 10kn a a  ;  0 22 ... 0kn a a , do ®ã 3 0 3(4 ) ...k kF n a u a u   vμ 2 0 2(2 ) ...k kF n a u a u   . Suy ra 2 1 0 2 1 2 0 2 1 0 1 (4 ) ( ) ... ( ) ( ... ) ( ... ) (2 ) ( ). k k k k k k k F n a u u a u u a u a u a u a u F n F n                  VËy (i) ®−îc chøng minh. V× 2 1u  nªn ta còng cã 3 0 3 2(4 2) ... (4 ) 1k kF n a u a u u F n       hay (ii) ®−îc chøng minh. Vμ cuèi cïng, v× 1 1u  nªn 2 0 2 1(2 1) ... (2 ) 1k kF n a u a u u F n       tøc lμ (iii) ®óng. Do (i)-(iii) x¸c ®Þnh duy nhÊt ( )F n nªn (*) chÝnh lμ c«ng thøc tæng qu¸t cña ( )F n . NhËn xÐt 3: NÕu trong biÓu diÔn nhÞ ph©n cña n kh«ng cã hai ch÷ sè 1 ®øng liÒn nhau (ta gäi lμ ch÷ sè 1 c« lËp) th× (3 ) (4 )F n F n . Chøng minh: Gi¶ sö trong biÓu diÔn nhÞ ph©n cña  0 2...kn a a kh«ng cã hai ch÷ sè 1 liªn tiÕp. V× 3 2n n n  mμ  0 22 ... 0kn a a nªn 3 2n n n      0 02 2... 0 ...k ka a a a . V× trong biÓu diÔn nhÞ ph©n cña  0 2...kn a a kh«ng cã hai ch÷ sè 1 liªn tiÕp nªn phÐp céng trªn lμ kh«ng cã nhí tõ hμng nμy sang hμng sau, tøc lμ nÕu  0 2...kn a a th×    0 02 23 2 ... 0 ...k kn n n a a a a    1 1 0 1 0( )...( )...( )k k k i ia a a a a a a a     . Do ®ã 1 0 1( ) ...k kf n a u a u   vμ 2 1 1 1 1 0 1 2 1 1 1 1 1 0 2 1 3 0 3 (3 ) ( ) ... ( ) ... ( ) ( ) .... ( ) ... ( ) ... (4 ). k k k k k i i i k k k k k k i i i k k f n a u a a u a a u a u a u u a u u a u u a u u a u a u F n                                   . 238 NhËn xÐt 4: Víi mäi n th× (3 ) (4 )F n F n . DÊu b»ng x¶y ra khi vμ chØ khi trong biÓu diÔn sè thËp ph©n cña n mäi ch÷ sè 1 lμ c« lËp. Chøng minh: Ta sÏ chøng minh nhËn xÐt 4 ®óng víi mäi 0 2mn  b»ng qui n¹p theo 1m  . Víi 1,2,3,4m  (0 16n  ) ®iÒu nμy dÔ dμng thÊy ®−îc qua b¶ng trªn. ThËt vËy: Víi 21 1n   : (3) (4) 2F F  ; Víi 22 10n   : (6) (8) 3F F  ; Víi 23 11n   : (9) 4 5 (12)F F   ; Víi 24 100n   : (12) (16) 5F F  . Gi¶ sö nhËn xÐt 4 ®óng víi mäi k m . Ta sÏ chøng minh nã ®óng víi 1k m  . Gi¶ sö 12 2m mn   . Khi Êy 2mn p  víi 0 2mp  . Gi¶ sö    1 2 1 0 1 2 1 02 2 2 2 100...00 ... 1 ...m m m m m m n p a a a a a a a a            . V×  1 2 1 0 2...m mp a a a a  (hÖ sè 1ma  kh«ng nhÊt thiÕt b»ng 0) nªn  1 2 1 0 24 ... 00m mp a a a a  vμ  1 2 1 0 24 1 ... 00m mn a a a a  . Do (*) ta cã: 3 1 2 2 1 1 4 0 3 3(4 ) ... (4 )m m m m m mF n u a u a u a u a u u F p             . XÐt ba tr−êng hîp: 1) 20 3 m p  . Khi Êy 3 2mp  , do ®ã  1 2 1 0 23 ...m mp b b b b  vμ     1 1 2 1 0 1 2 1 02 2 1 2 2 3 3(2 ) 2 2 3 100...00 100...00 ... 11 ... m m m m m m m m m n p p b b b b b b b b                          V× 0 2mp  nªn theo gi¶ thiÕt qui n¹p ta cã (3 ) (4 )F p F p . Do ®ã, tõ (*) suy ra 2 1 1 2 1 1 2 0 1 3 3 (3 ) ... (3 ) (4 ) (4 ). m m m m m m m m F n u u b u b u b u b u u F p u F p F n                    §¼ng thøc x¶y ra khi vμ chØ khi (3 ) (4 )F p F p , nghÜa lμ nÕu c¸c ch÷ sè 1 cña p lμ c« lËp. Nh−ng v× 2mn p  víi 0 2mp  nªn c¸c 239 ch÷ sè 1 cña n còng lμ c« lËp. VËy (3 ) (4 )F n F n khi vμ chØ khi c¸c ch÷ sè 1 cña n lμ c« lËp. 2) 12 2 3 3 m m p    . Khi Êy 3 2mp h  víi 0 2mh  nªn ta cã biÓu diÔn nhÞ ph©n     1 2 1 0 1 2 1 02 2 2 3 10...0 ... 1 ...m m m m m p h h h h h h h h          . Do ®ã 1 1 2 1 1 2 0 1 1 (3 ) ... ( ). m m m m m m F p u h u h u h u h u u F h              V×     1 1 2 1 0 1 2 1 02 2 1 2 2 3 3(2 ) 2 2 3 100...00 100...00 1 ... 100 ... m m m m m m m m m n p p h h h h h h h h                          nªn theo (*) vμ qui n¹p ta cã 3 1 2 1 1 2 0 1 3 3 1 2 2 3 (3 ) ... ( ) (3 ) (3 ) (4 ) (4 ) (4 ). m m m m m m m m m m m F n u h u h u h u h u u F h u F p u u F p u F p u F p F n                             Trong tr−êng hîp nμy dÊu b»ng kh«ng bao giê x¶y ra. 3) 12 2 3 m mp    . Khi Êy 12 3 3.2m mp   vμ 13 2mp q  víi 0 2mq  nªn ta cã biÓu diÔn nhÞ ph©n     1 2 1 0 1 2 1 02 2 1 2 3 10...0 ... 10 ...m m m m m p q q q q q q q q           . Do ®ã 2 1 2 1 1 2 0 1 2(3 ) ... ( ).m m m m m mF p u q u q u q u q u u F q            V×     1 1 2 1 0 1 2 1 02 2 1 2 2 3 3(2 ) 2 2 3 100...00 100...00 10 ... 101 ... m m m m m m m m m n p p q q q q q q q q                          nªn theo (*) vμ qui n¹p ta cã 240 3 1 1 2 1 1 2 0 1 3 1 3 1 2 3 (3 ) ... ( ) (3 ) (4 ) (4 ). m m m m m m m m m m m m F n u u q u q u q u q u u u F q u u F p u u F p F n                             DÊu b»ng kh«ng x¶y ra. Nh− vËy, trong mäi tr−êng hîp ta ®Òu cã (3 ) (4 )F n F n . DÊu b»ng x¶y ra khi vμ chØ khi 20 3 m p  vμ p chØ cã c¸c ch÷ sè 1 c« lËp. Lóc ®ã c¸c ch÷ sè 1 trong n còng lμ c« lËp. B©y giê ta cßn ph¶i chøng minh r»ng cã 12 (2 ) m mu F    sè nguyªn d−¬ng n trong kho¶ng 0;2m , víi c¸c ch÷ sè 1 bÞ c« lËp trong biÓu diÔn nhÞ ph©n cña chóng. ThËt vËy, víi 1m  ta cã hai sè 0 vμ 1 vμ 3 2u  ; víi 2m  ta cã ba sè 0; 1 vμ 3=102 lμ nh÷ng sè víi c¸c ch÷ sè 1 bÞ c« lËp trong biÓu diÔn nhÞ ph©n vμ 4 3u  . Gi¶ sö ®iÒu nμy ®óng víi mäi k m . Ta chøng minh nã ®óng víi k m . Gi¶ sö 2mn  vμ  1 0 2...mn a a . Khi Êy 12mn  khi vμ chØ khi 1 0ma   . Trong tr−êng hîp nμy theo qui n¹p ta cã 1mu  sè víi c¸c ch÷ sè 1 c« lËp. NÕu 12 2m mn   th× 1 1ma   , do ®ã 2 0ma   vμ l¹i theo qui n¹p ta cã mu sè víi c¸c ch÷ sè 1 c« lËp. VËy trong tÊt c¶ c¸c sè trong kho¶ng 0 2mn  cã tæng céng 1 1 2 (2 ) m m m mu u u F      sè víi c¸c ch÷ sè 1 c« lËp. 241 Tμi liÖu [1] Ph¹m Huy §iÓn, §inh ThÕ Lôc, T¹ Duy Ph−îng: H−íng dÉn thùc hμnh tÝnh to¸n trªn ch−¬ng tr×nh Maple V, Nhμ xuÊt b¶n Gi¸o dôc, Hμ Néi, 1998. [2] Ph¹m Huy §iÓn, Hμ Huy Kho¸i: M· hãa th«ng tin: C¬ së to¸n häc vμ øng dông, Nhμ xuÊt b¶n §¹i häc Quèc Gia, Hμ Néi, 2004. [3] Hμ Huy Kho¸i: Sè häc thuËt to¸n, Nhμ xuÊt b¶n Khoa häc KÜ thuÊt, Hμ Néi, 1996. [4] Hμ Huy Kho¸i, Ph¹m Huy §iÓn: Sè häc & thuËt to¸n, Nhμ xuÊt b¶n §¹i häc Quèc Gia, Hμ Néi, 2003. [5] S. V. Phomin: HÖ tÝnh, Nhμ xuÊt b¶n Nauka, Moscow, 1987 (TiÕng Nga). [6] T¹ Duy Ph−îng: Chuyªn ®Ò båi d−ìng häc sinh giái Gi¶i to¸n trªn m¸y tÝnh ®iÖn tö: HÖ ®Õm vμ øng dông, Nhμ xuÊt b¶n Gi¸o dôc, 2007.