Verbindingscriteria en scheidingsgraden

De vraag over het getal van Erdős die vorige week werd gesteld, was een kleine grap – en tevens een klein eerbetoon – aan de commentatoren die met hun diepgaande bijdragen van The Game of Science meer maken dan slechts een sectie logisch-wiskundige puzzels. Het is tevens een rechtvaardiging van de recreatieve wiskunde, aangezien ideeën niet alleen in de papers van academische publicaties worden verzonnen. Mijn Erdősgetal is 3, omdat ik heb samengewerkt met Raymond Smullyan, wiens nE 2 is (hij werkte niet rechtstreeks samen met Erdős, maar wel met enkele van zijn medewerkers). Daarom verdienen degenen die de afgelopen tien jaar aan deze sectie hebben bijgedragen terecht een nE van 4 (minstens). Zoals Juan Zubieta zegt: "Als deelname aan dit forum door een oplossing bij te dragen als een bijdrage wordt beschouwd, wed ik dat we genoeg vingers hebben om ons Erdősgetal te tellen."

Het getal van Erdős heeft betrekking op de bekende theorie van de zes graden van scheiding, volgens welke elke persoon met een andere persoon verbonden is via een keten van niet meer dan vijf tussenpersonen. Uiteraard hangt het allemaal af van ons basisconcept van verbinding: iemand kennen is niet hetzelfde als met hem of haar samenwerken aan een artikel. Of aan een film, want er is ook het getal van Bacon: nB 1 komt overeen met degenen die met de productieve acteur Kevin Bacon aan een film hebben meegewerkt, nB 2 met degenen die met een van hen hebben samengewerkt, enzovoort.

Een merkwaardige anekdote: er zijn nogal wat mensen die beide getallen tegelijk hebben, vandaar dat er ook het Erdős-Bacon-getal bestaat, dat de som van beide is. Richard Feynman (die in de film Anti-Clock speelde) heeft bijvoorbeeld een nEB = 6 (3 + 3). Die is overigens ook van mij (helaas is het het enige waarmee ik de grote Feynman kan evenaren).

Er zijn relevante mensen in elk vakgebied, en verschillende verbindingscriteria kunnen worden gebruikt om interessante, of op zijn minst merkwaardige, "getallen" te bepalen. Bijvoorbeeld, je Sinner-getal is 1 als je met de nummer één van de wereld hebt getennist, 2 als je met iemand hebt gespeeld die met hem heeft gespeeld... Ik nodig mijn oplettende lezers uit om met nieuwe, interessante "getallen" te komen.

De stelling van Erdős-Szekeres

Met betrekking tot de stelling van Erdős-Szekeres gelooft Francisco Montesinos dat "het niet zo ingewikkeld is als het op het eerste gezicht lijkt. Het idee, beschreven als het meest slimme door een goede kenner van de verschillende bewijzen van de stelling, bestaat uit het associëren van elke eindige reeks natuurlijke getallen N1, N2, ... N(n) van grootte n = (r-1)(s-1), waarbij r en s twee natuurlijke getallen zijn, een andere reeks van dezelfde grootte: p1, p2, ... p(n), waarbij p(i) = [a(i), b(i)] een geordend paar getallen is dat op de volgende manier is verkregen: p1 = (1, 1) en gedefinieerd als p(i) = [a(i), b(i)], stellen we p (i+1) = [ a (i)+1, b (i)] in als in de gegeven reeks N(i+1) > N(i), en p(i+1) = [a(i), b(i)+1] Anders nemen we aan dat in de gegeven reeks alle termen verschillend zijn.

Omdat de reeks {p(i)} bestaat uit n = (r-1)(s-1) termen, die labels worden genoemd, is het duidelijk dat, als in geen van deze labels een r of een s voorkomt, het toevoegen van een nieuwe term aan de gegeven reeks noodzakelijkerwijs zal resulteren in een label met óf een r óf een s , wat de stelling bewijst.”

FM heeft gelijk, het is niet zo ingewikkeld als het op het eerste gezicht lijkt: het is ingewikkelder. Maar ondanks de hoge temperaturen is het de moeite waard om er even een paar minuten mentaal in te duiken, want het is echt een slim idee.