Teorema lui Beatty

Teorema lui Beatty este o teorema de aritmetică publicată în 1926 de matematicianul canadian Samuel Beatty (dar menționat de Lord Rayleigh în 1894) , care prevede o condiție necesară și suficientă pe două reale pentru cele două apartamente „ Beatty “ asociat partitionnent ℕ *.

State

El afirmă echivalența următoarelor două puncte, pentru două numere reale și strict pozitive: $p$ $q$

Numerele și sunt iraționale și verificate $p$ $q$ ${\ displaystyle {\ frac {1} {p}} + {\ frac {1} {q}} = 1.}$
Cele două secvențe de numere întregi și , numite „Beatty suites”, formează o partiție a ansamblului ℕ *. ${\ displaystyle P = (\ mathrm {E} (np)) _ {n \ in \ mathbb {N} ^ {*}}}$ ${\ displaystyle Q = (\ mathrm {E} (nq)) _ {n \ in \ mathbb {N} ^ {*}}}$

Aici, funcția $E$ denotă funcția întreagă .

Demonstrație

Dăm lui p și q două reale strict pozitive, astfel încât secvențele P și Q formează o partiție a lui ℕ *.

Rezultatul devine destul de intuitiv dacă introducem densitatea unei părți A a lui ℕ *, este limita - dacă există - atunci când n tinde spre de . De exemplu, setul de numere pare (sau setul de numere impare) are o densitate care este 1/2, setul de numere prime are o densitate de 0. $+ \ infty$ ${\ displaystyle {\ frac {{\ textrm {card}} A \ cap \ {1, \ dots, n \}} {n}}}$

Putem vedea cu ușurință că mulțimile unde este un real pozitiv au densitate . Suporturile secvențelor P și Q formează o partiție a lui ℕ *, deci suma densităților lor este egală cu 1: ${\ displaystyle \ {E (n \ alpha), n \ in \ mathbb {N} ^ {*} \}}$ $\alfa$ ${\ displaystyle {\ frac {1} {\ alpha}}}$

{\ displaystyle {\ frac {1} {p}} + {\ frac {1} {q}} = 1}

Mai mult, p și q nu pot fi ambele raționale, pentru că dacă este , atunci . Cu toate acestea, secvențele P și Q nu au niciun element în comun. Unul dintre cele două este irațional și, prin urmare, ambele sunt iraționale (pentru că ) ${\ displaystyle p = {\ frac {a_ {1}} {b_ {1}}}, q = {\ frac {a_ {2}} {b_ {2}}}}$ ${\ displaystyle E (b_ {1} a_ {2} p) = E (b_ {2} a_ {1} q) (= a_ {1} a_ {2})}$ $p ^ {{- 1}} + q ^ {{- 1}} = 1$

În schimb, dacă p și q sunt iraționale și , să arătăm prin absurd că suporturile secvențelor P și Q sunt disjuncte. Fie k un număr întreg care este scris în formă . $p ^ {{- 1}} + q ^ {{- 1}} = 1$ ${\ displaystyle k = E (np) = E (mq)}$

Prin definiția părții întregi, avem următoarele inegalități:

{\ displaystyle k \ leq np <k + 1 {\ mbox {și}} k \ leq mq <k + 1}

Să împărțim prima inegalitate la p, iar a doua la q:

{\ displaystyle {\ frac {k} {p}} \ leq n <{\ frac {k} {p}} + {\ frac {1} {p}} {\ mbox {et}} {\ frac {k } {q}} \ leq m <{\ frac {k} {q}} + {\ frac {1} {q}}}

Adăugați aceste două inegalități, obținem:

{\ displaystyle k \ leq n + m <k + 1}

k, n și m fiind numere întregi, acest lucru impune că . Există neapărat egalitate în cele două inegalități precedente [de ce?] . Deci k = np și k = mq. Acest lucru este absurd deoarece p și q sunt iraționale. ${\ displaystyle k = n + m}$

Să arătăm acum că orice număr natural diferit de zero este atins de una dintre cele două secvențe. Fie și k = E (np). k este atins de secvența P, deci nu de secvența Q, există un număr întreg m astfel încât: $n \ geq 1$

{\ displaystyle E (mq) <k <E ((m + 1) q)}

De fapt, întregul E (mq) este cel mai mare întreg al secvenței Q mai mic decât k. Hărțile și sunt injective deoarece p și q sunt mai mari decât 1. Intervalul conține, prin urmare, elemente ale secvențelor P și Q (deoarece aceste două secvențe au suporturi disjuncte). Este suficient să încheiem dovedind k = n + m. Avem : ${\ displaystyle r \ mapsto E (rp)}$ ${\ displaystyle r \ mapsto E (rq)}$ ${\ displaystyle \ {1, \ dots, k \}}$ $m + n$

{\ displaystyle {\ frac {k} {p}} \ leq n <{\ frac {k + 1} {p}} {\ mbox {et}} {\ frac {k} {q}} - 1 <m <{\ frac {k + 1} {q}}}

Adăugând că vine , așa să fie . CQFD . ${\ displaystyle k-1 <n + m <k + 1}$ ${\ displaystyle k = n + m}$

Acest rezultat nu se generalizează: este imposibil să partiționăm ℕ * cu trei sau mai multe secvențe ale acestei forme.

Exemplu

Unul dintre cele mai vechi exemple cunoscute a fost descoperit încă din 1907 de matematicianul olandez Wythoff , independent de teorema lui Beatty. Pentru raportul de aur , avem: $\ phi$

{\ displaystyle {\ frac {1} {\ phi}} + {\ frac {1} {\ phi ^ {2}}} = 1 \,.}

Cele două secvențe obținute sunt apoi:

${\ displaystyle {\ rm {E}} (n \ phi)}$ , n > 0: 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... suite A000201 din OEIS
${\ displaystyle {\ rm {E}} (n \ phi ^ {2})}$ , n > 0: 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... suite A001950 a OEIS

Perechile apar în rezoluția jocului lui Wythoff și caracterizează pozițiile din care jucătorul care are trăsătura nu poate câștiga. ${\ displaystyle ({\ rm {E}} (n \ phi), {\ rm {E}} (n \ phi ^ {2}))}$

Referinţă

Serge Francinou, Hervé Gianella și Serge Nicolas, Exerciții de matematică, X-ENS oral. Algebra 1 , Cassini

Vezi și tu

Articole similare

Cuvânt sturmian
Teorema Lambek-Moser (ro)

Link extern

Pagini care conțin applet-uri pentru a calcula termenii secvenței Beatty sau pentru a determina p și q conform termenilor secvenței