Prouhet-Tarry-Escott-ongelma
Vuonna matematiikan , erityisesti lukuteoria ja combinatorics The ongelma Prouhet-Jää-Escott on löytää jokaiselle kokonaisluku , kaksi ja sekä kokonaislukuja, kuten:
ei{\ displaystyle n}
AT{\ displaystyle A}
B{\ displaystyle B}
ei{\ displaystyle n}![ei](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
∑klo∈ATkloi=∑b∈Bbi{\ displaystyle \ summa _ {a \ sisään A} a ^ {i} = \ summa _ {b \ B} b ^ {i}}![\ summa _ {{a \ A}} a ^ {i} = \ summa _ {{b \ B}} b ^ {i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd7e50f14b81a3bd86382d4f1ed00822ec80799a)
Kunkin ja jopa tietyn kokonaisluku . Jos ja vahvista nämä ehdot, kirjoitamme .
i{\ displaystyle i}
1{\ displaystyle 1}
k{\ displaystyle k}
AT{\ displaystyle A}
B{\ displaystyle B}
AT=kB{\ displaystyle A = _ {k} B}![A = _ {k} B](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3b7429de06dbcbb0ff599962add7043806e192c)
Etsimme ratkaisua, joka on vähimmäiskoko tietylle tutkinnolle . Tämä edelleen avoin ongelma on nimetty Eugène Prouhet , joka tutki sitä vuonna 1851, ja Gaston Tarry ja Edward Brind Escott, jotka pitivät sitä 1910-luvun alussa.
ei{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Suurin arvo, jolle tiedämme ratkaisun, on . Vastaava ratkaisu saadaan seuraavista sarjoista:
k{\ displaystyle k}
ei=k+1{\ displaystyle n = k + 1}
k=11{\ displaystyle k = 11}![k = 11](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e4592ab141206fc0a5d323c4c06661991256a47)
AT={±22,±61,±86,±127,±140,±151} ,B={±35,±47,±94,±121,±146,±148}{\ displaystyle A = \ {\ pm 22, \ pm 61, \ pm 86, \ pm 127, \ pm 140, \ pm 151 \} \, qquad B = \ {\ pm 35, \ pm 47, \ pm 94, \ pm 121, \ pm 146, \ pm 148 \}}
Esimerkki
Määritelmän kokonaisluku on aste ja kokonaisluku on koko . On helppo nähdä, että mihin tahansa ratkaisuun meillä on . Etsimme siis vähimmäiskokoa.
k{\ displaystyle k}
ei{\ displaystyle n}
ei>k{\ displaystyle n> k}![n> k](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8afbc0693bee3f48a31d2c991ddc8b6b4a35322)
Koko ja aste , molemmat sarjat
ei=6{\ displaystyle n = 6}
k=5{\ displaystyle k = 5}![k = 5](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcf68fa52735a07a4e91b5735726a88f79bee969)
{0,5,6,16,17,22}{\ displaystyle \ {0,5,6,16,17,22 \}}![\ {0,5,6,16,17,22 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d32a6ceed5eb2032cfd969a83fa477172b919329)
ja
{1,2,10,12,20,21}{\ displaystyle \ {1,2,10,12,20,21 \}}
ovat ratkaisu ongelmaan, koska:
0+5+6+16+17+22=66=1+2+10+12+20+21{\ displaystyle 0 + 5 + 6 + 16 + 17 + 22 = 66 = 1 + 2 + 10 + 12 + 20 + 21}
02+52+62+162+172+222=1090=12+22+102+122+202+212{\ displaystyle 0 ^ {2} + 5 ^ {2} + 6 ^ {2} + 16 ^ {2} + 17 ^ {2} + 22 ^ {2} = 1090 = 1 ^ {2} + 2 ^ { 2} + 10 ^ {2} + 12 ^ {2} + 20 ^ {2} + 21 ^ {2}}
03+53+63+163+173+223=19998=13+23+103+123+203+213{\ displaystyle 0 ^ {3} + 5 ^ {3} + 6 ^ {3} + 16 ^ {3} + 17 ^ {3} + 22 ^ {3} = 19998 = 1 ^ {3} + 2 ^ { 3} + 10 ^ {3} + 12 ^ {3} + 20 ^ {3} + 21 ^ {3}}
04+54+64+164+174+224=385234=14+24+104+124+204+214{\ displaystyle 0 ^ {4} + 5 ^ {4} + 6 ^ {4} + 16 ^ {4} + 17 ^ {4} + 22 ^ {4} = 385234 = 1 ^ {4} + 2 ^ { 4} + 10 ^ {4} + 12 ^ {4} + 20 ^ {4} + 21 ^ {4}}
05+55+65+165+175+225=7632966=15+25+105+125+205+215{\ displaystyle 0 ^ {5} + 5 ^ {5} + 6 ^ {5} + 16 ^ {5} + 17 ^ {5} + 22 ^ {5} = 7632966 = 1 ^ {5} + 2 ^ { 5} + 10 ^ {5} + 12 ^ {5} + 20 ^ {5} + 21 ^ {5}}![0 ^ {5} + 5 ^ {5} + 6 ^ {5} + 16 ^ {5} + 17 ^ {5} + 22 ^ {5} = 7632966 = 1 ^ {5} + 2 ^ {5} + 10 ^ {5} + 12 ^ {5} + 20 ^ {5} + 21 ^ {5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ece61016f4b73df04aba4427a4e63bfb6d68491b)
.
Ihanteellinen ratkaisu on ratkaisu, jonka koko on yhtä suuri kuin aste +1, joten yllä oleva ratkaisu on ihanteellinen.
Historia
Vuonna 1851 Eugène Prouhet esitti yleisemmän ongelman jakamalla kokonaisluvut x 1: stä n m : een n luokkaan niin, että kunkin luokan kokonaislukujen k-s: n tehojen summa on sama, kun k = 0, 1 , ... menetelmä hän aikoo määrät numeroinnin luokkiin 0 n - 1, hajottamiseksi kukin kokonaisluku x - 1 määrän pohja n , täsmää sen numeroa, laskea jäljellä r tästä määrästä modulo n ja määritä kokonaisluku x luokalle r .
Tapauksessa, jossa n = 2, kokonaisluvun x sijoittaminen toiseen kahdesta indeksin 0 tai 1 luokasta tapahtuu sen mukaan, onko Prouhet-Thue-Morse-sekvenssin x- kolmas termi 0 vai 1. ensimmäiset 8 kokonaislukua on jaettu yhtäältä: 1, 4, 6, 7 ja toisaalta 2, 3, 5, 8, ja näiden kahden luokan kokonaislukujen k- osien summa yhtenevät, kunnes k = 2.
Leonard Eugene Dickson omistaa kappaleen hänen History of Number Theory on " Sarjaa kokonaislukuja yhtä summia kuten valtuuksia " , ja luettelot peräti 70 artikkelia tästä aiheesta. Edward Maitland Wright toteaa historiallisessa artikkelissaan, että Prouhetin artikkeli löydettiin uudelleen vasta vuonna 1948.
Peter Borwein ja hänen kirjoittajansa kuvaavat viimeaikaista kehitystä . katso myös Filasetan ja Markovichin artikkeli. Alpers ja Tijdeman (2007) ovat tutkineet kaksiulotteista versiota .
Ominaisuudet ja tulokset
- Jos pari ja on tutkintoratkaisu , niin kaikille ja kaikille pariskunnilleAT={klo1,klo2,...,kloei}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}
B={b1,b2,...,bei}{\ displaystyle B = \ {b_ {1}, b_ {2}, \ ldots, b_ {n} \}}
k{\ displaystyle k}
EI≠0{\ displaystyle N \ neq 0}
M{\ displaystyle M}
AT′={EIklo1+M,EIklo2+M,...,EIkloei+M}etB′={EIb1+M,EIb2+M,...,EIbei+M}{\ displaystyle A '= \ {Na_ {1} + M, Na_ {2} + M, \ ldots, Na_ {n} + M \} \ quad {\ rm {ja}} \ quad B' = \ {Nb_ {1} + M, Nb_ {2} + M, \ ldots, Nb_ {n} + M \}}
on edelleen saman asteen ratkaisu. Joten ratkaisu{0,5,6,16,17,22}=5{1,2,10,12,20,21}{\ displaystyle \ {0,5,6,16,17,22 \} = _ {5} \ {1,2,10,12,20,21 \}}
antaa myös ratkaisun{1,6,7,17,18,23}=5{2,3,11,13,21,22}.{\ displaystyle \ {1,6,7,17,18,23 \} = _ {5} \ {2,3,11,13,21,22 \}.}
Tämän havainnon avulla voidaan standardoida ratkaisut asettamalla esimerkiksi, että ne sisältävät vain positiivisia tai nolla kokonaislukuja, ja että nolla esiintyy niissä.
- Emme tiedä ihanteellista ratkaisua jokaiselle tutkinnolle, mutta tiedämme, että jokaiselle tutkinnolle on kooltaan sopiva ratkaisu .k{\ displaystyle k}
ei≤k(k+1)/2+1{\ displaystyle n \ leq k (k + 1) / 2 + 1}![n \ leq k (k + 1) / 2 + 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/364201e1e9a86a13e48d26c1ac3e065979905e96)
- Symmetriset ratkaisut: Tasakokoinen ratkaisu on symmetrinen, jos jokainen komponentti on muodoltaanei=2m{\ displaystyle n = 2m}
{±vs.1,±vs.2,...,±vs.m}.{\ displaystyle \ {\ pm c_ {1}, \ pm c_ {2}, \ ldots, \ pm c_ {m} \}.}
Johdannossa annettu ratkaisu on tässä muodossa.
- Pariton kokoinen ratkaisu on symmetrinen, jos ratkaisun komponentit ovat vastakkaisia, ts.AT={klo1,klo2,...,kloei}{\ displaystyle A = \ {a_ {1}, a_ {2}, \ ldots, a_ {n} \}}
ja B={-klo1,-klo2,...,-kloei}.{\ displaystyle B = \ {- a_ {1}, - a_ {2}, \ ldots, -a_ {n} \}.}
Ihanteelliset ja symmetriset ratkaisut
Ihanteelliset ja symmetriset ratkaisut tunnetaan tutkinnoista lukuun ottamatta seuraavia :
k≤11{\ displaystyle k \ leq 11}
k=10{\ displaystyle k = 10}![k = 10](https://wikimedia.org/api/rest_v1/media/math/render/svg/b698dab3ec76554ed1b958de53897071b95f5bdb)
- k=1{\ displaystyle k = 1}
![k = 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c035ffa69b5bca8bf2d16c3da3aaad79a8bcbfa)
{±2}=1{±1}{\ displaystyle \ {\ pm 2 \} = _ {1} \ {\ pm 1 \}}![\ {\ pm 2 \} = _ {1} \ {\ pm 1 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5533228c16c31cd0c43f822384ad8717592e1bca)
- k=2{\ displaystyle k = 2}
![k = 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd301789e1f25a3da4be297ff637754ebee5f5d)
{-2,-1,3}=2{2,1,-3}{\ displaystyle \ {- 2, -1,3 \} = _ {2} \ {2.1, -3 \}}![\ {- 2, -1,3 \} = _ {2} \ {2,1, -3 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0774e18731bb2bf59378f16351868ff4488951c2)
- k=3{\ displaystyle k = 3}
![k = 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/662e06a2436f8a44fec791f5c794621f10dc8f30)
{±3,±11}=3{±7,±9}{\ displaystyle \ {\ pm 3, \ pm 11 \} = _ {3} \ {\ pm 7, \ pm 9 \}}![\ {\ pm 3, \ pm 11 \} = _ {3} \ {\ pm 7, \ pm 9 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c6522e9caf00ee1f681c65396bbe1ba66125535)
- k=4{\ displaystyle k = 4}
![k = 4](https://wikimedia.org/api/rest_v1/media/math/render/svg/b96ee1f0df5aee064133a126f203a7d84e50e19b)
{-8,-7,1,5,9}=4{8,7,-1,-5,-9}{\ displaystyle \ {- 8, -7,1,5,9 \} = _ {4} \ {8,7, -1, -5, -9 \}}![\ {- 8, -7,1,5,9 \} = _ {4} \ {8,7, -1, -5, -9 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46ae78da5ec5d01a66457b8eb9a49cdf5dfd79b5)
- k=5{\ displaystyle k = 5}
![k = 5](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcf68fa52735a07a4e91b5735726a88f79bee969)
{±4,±9,±13}=5{±1,±11,±12}{\ displaystyle \ {\ pm 4, \ pm 9, \ pm 13 \} = _ {5} \ {\ pm 1, \ pm 11, \ pm 12 \}}![\ {\ pm 4, \ pm 9, \ pm 13 \} = _ {5} \ {\ pm 1, \ pm 11, \ pm 12 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0950d0153c8e72ce68eb111cc7836a5fdf88030)
- k=6{\ displaystyle k = 6}
![k = 6](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5f6d9900d6ecc8ff1bdb37886c8b5fc93ed3713)
{-51,-33,-24,7,13,38,50}=6{51,33,24,-7,-13,-38,-50}{\ displaystyle \ {- 51, -33, -24,7,13,38,50 \} = _ {6} \ {51,33,24, -7, -13, -38, -50 \}}![\ {- 51, -33, -24,7,13,38,50 \} = _ {6} \ {51,33,24, -7, -13, -38, -50 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07371b72e934ae577acce697d5a02ff5fbbb8346)
- k=7{\ displaystyle k = 7}
![k = 7](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc8926bffa41d9b33e0e7c9c273ed34e46cef580)
{±2,±16,±21,±25}=7{±5,±14,±23,±24}{\ displaystyle \ {\ pm 2, \ pm 16, \ pm 21, \ pm 25 \} = _ {7} \ {\ pm 5, \ pm 14, \ pm 23, \ pm 24 \}}![\ {\ pm 2, \ pm 16, \ pm 21, \ pm 25 \} = _ {7} \ {\ pm 5, \ pm 14, \ pm 23, \ pm 24 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd12314424065846e2a5c22d368dfe5da675b822)
- k=8{\ displaystyle k = 8}
![k = 8](https://wikimedia.org/api/rest_v1/media/math/render/svg/1170deafc5d96c9d76fcd097806d334487cddc1f)
{-98,-82,-58,-34,13,16,69,75,99}=8{98,82,58,34,-13,-16,-69,-75,-99}{\ displaystyle \ {- 98, -82, -58, -34,13,16,69,75,99 \} = _ {8} \ {98,82,58,34, -13, -16, - 69, -75, -99 \}}![\ {- 98, -82, -58, -34,13,16,69,75,99 \} = _ {8} \ {98,82,58,34, -13, -16, -69, - 75, -99 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30fb44df5d5a4b7a7b9cecc3db1e65c5aeb0dfd3)
- k=9{\ displaystyle k = 9}
![k = 9](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f8bbb3cb20c420011735af8ba728e3cbea6e620)
{±99,±100,±188,±301,±313}=9{±71,±131,±180,±307,±308}{\ displaystyle \ {\ pm 99, \ pm 100, \ pm 188, \ pm 301, \ pm 313 \} = _ {9} \ {\ pm 71, \ pm 131, \ pm 180, \ pm 307, \ pm 308 \}}![\ {\ pm 99, \ pm 100, \ pm 188, \ pm 301, \ pm 313 \} = _ {9} \ {\ pm 71, \ pm 131, \ pm 180, \ pm 307, \ pm 308 \ }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecc43d0ce94c22c51bbf012d723ae675c42a5a6d)
Tämä viimeinen ratkaisu annetaan yhdessä muiden kanssa Borwein et ai. (2003) . Ihanteellista ratkaisua ei tunneta .
k=10{\ displaystyle k = 10}![k = 10](https://wikimedia.org/api/rest_v1/media/math/render/svg/b698dab3ec76554ed1b958de53897071b95f5bdb)
Algebrallinen muotoilu
On algebrallisempi tapa muotoilla ongelma:
Ehdotus - Seuraavat ehdot vastaavat:
- ∑i=1eikloij=∑i=1eibij,(j=1,...,k){\ displaystyle \ summa _ {i = 1} ^ {n} a_ {i} ^ {j} = \ summa _ {i = 1} ^ {n} b_ {i} ^ {j}, \ quad (j = 1, \ ldots, k)}
![\ summa _ {{i = 1}} ^ {n} a_ {i} ^ {j} = \ summa _ {{i = 1}} ^ {n} b_ {i} ^ {j}, \ quad (j = 1, \ ldots, k)](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e6be24cad1a51b6da0038b1769198c1f23b8b57)
- deg(∏i=1ei(x-kloi)-∏i=1ei(x-bi))≤ei-(k+1){\ displaystyle \ deg \ left (\ prod _ {i = 1} ^ {n} (x-a_ {i}) - \ prod _ {i = 1} ^ {n} (x-b_ {i}) \ oikea) \ leq n- (k + 1)}
![\ deg \ vasen (\ prod _ {{i = 1}} ^ {n} (x-a_ {i}) - \ prod _ {{i = 1}} ^ {n} (x-b_ {i}) \ oikea) \ leq n- (k + 1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/16cfe5ca2cbab5acff9c527637de1e22bb69a4af)
- (x-1)k+1|∑i=1eixkloi-∑i=1eixbi.{\ displaystyle (x-1) ^ {k + 1} \ vasen | \ summa _ {i = 1} ^ {n} x ^ {a_ {i}} - \ summa _ {i = 1} ^ {n} x ^ {b_ {i}} \ oikea ..}
![(x-1) ^ {{k + 1}} \ vasen | \ summa _ {{i = 1}} ^ {n} x ^ {{a_ {i}}} - \ summa _ {{i = 1} } ^ {n} x ^ {{b_ {i}}} \ oikea ..](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fa361f2c01d5ea6f361b867b6c5bfb710aaa58c)
Huomautuksia ja viitteitä
(fr) Tämä artikkeli on osittain tai kokonaan peräisin
englanninkielisestä Wikipedia- artikkelista
" Prouhet - Tarry - Escott-ongelma " ( katso luettelo kirjoittajista ) .
Huomautuksia
-
Borwein (2002) , s. 85
-
Nuutti Kuosan, Jean-Charles Meyrignacin ja Chen Shuwenin vuonna 1999 antama ratkaisu , katso The Prouhet-Tarry-Escott -ongelma .
-
ME Prouhet, Muistio joistakin numeroiden voimien välisistä suhteista , CR Acad. Sci. Pariisi, sarja I, voi. 33, 1851, s. 225 .
-
(in) Leonard Eugene Dickson , historia teorian Numbers (fi) [ yksityiskohta painokset ], lento. 2, 1919, c. XXIV, s. 705-716 .
-
Wright (1959)
-
Borwein ja Ingalls (1944)
-
Borwein (2002)
-
Borwein, Lisonĕk ja Percival 2003
-
(in) Michael Filaseta ja Maria Markovich , " Newton polygoneja ja Prouhet-Jää-Escott ongelma " , Journal of Number Theory , vol. 174,
2017, s. 384–400 ( DOI 10.1016 / j.jnt.2016.10.009 ).
-
Borwein (2002) ja The Prouhet-Tarry-Escott -ongelma .
-
Katso viitteitä Borwein ja Ingalls (1944) .
Viitteet
- (en) Andreas Alpers ja Robert Tijdeman , " Kaksiulotteinen Prouhet-Tarry-Escott-ongelma " , J. Number Theor. , voi. 123,2007, s. 403-412
-
(en) Peter Borwein , laskennalliset retket analyysissä ja numeroteoriassa , New York / Berliini / Heidelberg, Springer , coll. "CMS-kirjat matematiikassa",2002, 220 Sivumäärä ( ISBN 0-387-95444-9 , lue verkossa )Luku 11: Prouhet - Tarry - Escott -ongelma (sivut 85-96) on omistettu ongelmalle.
- (en) Peter Borwein ja Colin Ingalls , ” Prouhet-Tarry-Escott -ongelma palasi ” , opettaja. Matematiikka. , voi. 40, n luu 1-2,1994, s. 3-27 ( lue verkossa )
- (en) Peter Borwein , Petr Lisonĕk ja Colin Percival , ” Prouhet-Tarry-Escott -ongelman laskennalliset tutkimukset ” , Math. Comp. , voi. 72, n ° 244,2003, s. 2063-2070 ( lue verkossa )
- (de) Albert Gloden (lb) , Mehrgradige Gleichungen: Mit einem Vorwort von Maurice Kraitchik , Groningen, P. Noordhoff,1944( Matemaattiset arvostelut 0019638 )
-
GH Hardy ja EM Wright ( englanniksi kääntänyt F. Sauvageot), Johdatus lukuteoriaan [“ Johdanto numeroiden teoriaan ”], Pariisi ja Heidelberg, Vuibert ja Springer2007Osa 20.5 “Neljän neliön lause” käsittelee tätä aihetta. Luvut 21.9 “Prouhetin ja Tarryn ongelma: numero ” ja 21.10, s. 423-427, on omistettu Prouhet-Tarryn ongelmalle.P(k,j){\ displaystyle P (k, j)}
- (en) Edward M. Wright , ” Prouhetin vuoden 1851 ratkaisu vuoden 1910 Tarry-Escott-ongelmaan ” , Amer. Matematiikka. Kuukausittain , vol. 66,Maaliskuu 1959, s. 199-201
Katso myös
Aiheeseen liittyvät artikkelit
Ulkoiset linkit
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">