Raggruppamenti forzati

[Sk_Anonymous]

Una riga di 1000 numeri è scritta alla lavagna.
Scriviamo una seconda riga di numeri sotto la prima, secondo la seguente regola: sotto ogni numero x scriviamo il numero naturale che indica quante volte x si trova nella prima linea.
Poi scriviamo una terza riga di numeri sotto la seconda, seguendo lastessa regola: sotto ogni numero y scriviamo il numero naturale che indica quante volte y si trova nella seconda linea.
E così via.
a) Dimostrare che c'è una riga uguale alla precedente.
b) Dimostrare che l'undicesima riga coincide con la dodicesima
c) Fornire un esempio di prima riga tale che la decima riga sia differente dalla undicesima riga.

[Pachisi]

Intanto provo la prima parte. Per le altre ci penso.

Osserviamo che leggendo dall'alto verso il basso dalla seconda riga in poi abbiamo sequenze di interi non decrescenti ma limitate (un numero non può esserci più di 1000 volte). Allora, da un certo punto in poi, le sequenze di interi saranno costanti. Dunque, da quel punto, le righe saranno uguali.
Spero sia abbastanza chiaro.

[axpgn]

"Pachisi":Intanto provo la prima parte. Per le altre ci penso.

... (un numero non può esserci più di 1000 volte) ...

mi pare che dalla seconda in poi al massimo ci sono $44$ numeri diversi

Cordialmente, Alex

[axpgn]

Penso che la "sequenza" più lunga di righe diverse sia quella che nasce da una riga iniziale composta da due numeri che compaiono una volta sola, un numero che compare due volte, un numero che compare quattro volte e così via fino a un numero che compare $256$ e l'ultimo che compare le restanti $488$.

Cordialmente, Alex

[orsoulx]

Alex, come al solito, pensa giusto. Si può dimostrare che iniziando con $ n $ numeri la sequenza più lunga di righe diverse non può essere maggiore di $ 2+log_2 n $.
Un piccolo rilancio di fine anno. Nella soluzione proposta vi sono numeri che compaiono una sola volta e un numero che compare $ 488 $ volte, con una differenza di $ 488-1=487 $. Qual è, sempre iniziando con mille numeri e con $ 11 $ righe diverse, il minimo valore possibile per questa differenza?
Ciao e Buon Anno a tutti
B.

[Sk_Anonymous]

non sono sicuro di aver capito bene la questione, ma in prima battuta proverei con il numero palindromo 383

[orsoulx]

Ogni riga è un insieme di mille numeri. Volendo ottenere 11 righe diverse, non importa quali siano i numeri della prima riga, ma solo le loro molteplicità, che saranno i numeri della seconda riga. Alex propone una soluzione nella quale, indicando con $ R_2 $ l'insieme dei numeri della seconda riga, è $ d=Max(R_2) - min(R_2)=487 $. Credo che questo sia il massimo valore possibile per $ d $. Chiedevo quale fosse, invece, il suo minimo: $ 383 $ mi pare troppo grande.

[axpgn]

Credo di aver capito ... invece di un numero ripetuto $488$ volte, nella prima riga ci va una lista di numeri, tutti diversi dagli altri della prima riga, le cui occorrenze siano tutte diverse dalle potenze di due (dalla zero alla ottava), tutte diverse fra loro e la cui somma (delle occorenze intendo) faccia $488$.
In tal modo la differenza tra max e min sarebbe $255$.
Per esempio una lista di numeri le cui istanze corrispondano alla sequenza dei primi da $3$ a $57$ più $52$ ...
Mi pare che possa funzionare ...

Cordialmente, Alex

[orsoulx]

@Alex
Funziona. Ma 255 non è ancora il minimo.
Ciao
B.

[Sk_Anonymous]

faccio un altro tentativo.
Sulla base del sito da cui ho preso il problema penso si possa arrivare a 1 0 3.

[orsoulx]

Se esiste una soluzione con $ d=103 $, il mio risultato $ d=127$ non è il minimo.
Riporto una possibile soluzione indicando le molteplicità dei numeri nella prima riga in ordine non decrescente:

$ 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5, 8, 8, 8, 9, 9, 10, 16, 16, 16, 18, 20, 32, 32, 32, 36, 40, 64, 64, 64, 80, 128, 128, 128. $

Ciao
B.

[axpgn]

Notevole!

Cordialmente, Alex

[Sk_Anonymous]

Il problema l'ho trovato all'interno di una lista intotitola I problemi irrisolti della "Collezione" di questo sito:

http://www.base5forum.it/quesiti-irrisolti-f2.html

e qua alcune mie considerazioni a riguardo:

http://www.base5forum.it/riga-di-1000-n ... fad564b338

[Sk_Anonymous]

"orsoulx":Se esiste una soluzione con $ d=103 $,

La "soluzione" a cui facevo riferimento non è 103, ma

"sprmnt21":Sulla base del sito da cui ho preso il problema penso si possa arrivare a 1 0 3.

qua:
http://www.base5forum.it/riga-di-1000-n ... 03839e73e4
si trova l'indicazione di una sequenza generatrice che potrebbe, tra l'altro, essere una base di una vera dimostrzione di minimalità e non solo di ingegnosi tentativi.

[orsoulx]

"sprmnt21":....si trova l'indicazione di una sequenza generatrice che potrebbe, tra l'altro, essere una base di una vera dimostrzione di minimalità e non solo di ingegnosi tentativi.

I quattro neuroni che mi son rimasti rischiano di scontrarsi. Non capisco per quale motivo, volendo conoscere le tue elucubrazioni, si debba compulsare la discussione di un altro sito (ottimo, ma purtroppo poco frequentato negli ultimi tempi) dove parli con te stesso. L'ultima che proponi mi pare pregevolissima, ma in cosa si differenzia dai nostri 'ingegnosi tentativi' (che probabilmente derivano da implicite assunzioni)?
1 0 3, era da interpretarsi come: ci sono degli 1, nessun 2 e dei 3' Boh!

[Sk_Anonymous]

il rimando all'altro sito (che costa solo un click, avendo fornito il link) è solo per "cortesia" verso il sito da cui ho preso il problema.

Il sito si chiama BASE 5 (non BASE 10, bada bene), lo frequentavo anni fa quando mi occupavo di matematica "dilettevole e curiosa".
Ero alla ricerca della mia soluzione sul problema delle "radici intere o spezzate" e sono capiatato nella sessione dove c'era quetso problema ancora irrisolto. Mi è venuta in mente una idea di possibile soluzione e l'ho voluat condividere con i frequentatori del sito, senza accorgermi che non sono più così tanti e attivi.

Sul perché ritenga questa sequenza più foriera di risultati generali, beh è solo una sensazione, derivante dalla struttura "regolare" della sequenza. Non credo che mi ci[ ]me[n/t]terò a cercare una prova generale di minimalità e volevo passare la mano a qualcun altro, magari più interessato alla questione.

Tutto qua.

[orsoulx]

Beh! Adesso ho capito. Bisognerebbe chiedere agli amministratori di inserire un nuovo tag [QUIZ] [/QUIZ] entro cui racchiudere quel che si gradirebbe venisse risolto dall'interlocutore. Mi pare eccessivo attendersi che venga risolto un giochino senza avvertire l'ignaro lettore del cambiamento di registro. Sull'altro sito avresti avuto qualche speranza in più.