Palline e Barrette

[sqrt2]

Date k barrette, si devono disporre su di esse delle palline numerate (1,2,3,4,...) una alla volta partendo dalla 1 e seguendo l'ordine dato dai numeri a esse associate, di modo che la somma dei numeri associati a due palline consecutive in una barretta sia un quadrato perfetto. Quando la n-esima pallina non può essere messa in nessuna barretta, ci si ferma. Esiste un k per cui si può procedere all'infinito?

[moebius]

I hope no

[sqrt2]

...grazie...una risposta piu' matematica?

[exodd]

nn capisco nemmeno ke kiede...

[moebius]

Avrei giurato fosse in combinatoria... boh!
BTW...

Supponiamo che esista un tale k. Allora presi k+1 numeri consecutivi, poichè almeno 2 vanno sulla stessa sbarretta, la somma di almeno due di essi deve essere un quadrato perfetto. Se trovo k numeri consecutivi per cui la somma di nessuna coppia di questi sia un quadrato perfetto ho un assurdo.
Tra n^2 ed (n+1)^2 ci sono 2n numeri che ovviamente non sono quadrati perfetti ed è li che voglio andare a piazzare le mie somme. Chiamiamo a il primo dei k+1 numeri consecutivi che sto cercando. Allora i miei numeri andranno da a ad a+k e quindi il minimo delle possibili somme varrà 2a+1, mentre il massimo 2(a+k)-1. Poichè li voglio mettere tutti dentro il buco tra due quadrati dovrà essere:
2(a+k)-1-2a-1 \leq 2n ossia n \geq k+1.
Quindi tra (k+1)^2 e (k+2)^2 c'è abbastanza spazio,così come tra (k+2)^2 e (k+3)^2. A questo punto basta prendere a tale che 2a+1=(k+1)^2+1, ossia a=(k+1)^2/2 se k è pari o a tale che 2a+1=(k+2)^2+1, ossia (k+2)^2/2 se k è dispari.
Ah si... e sperare di non aver scritto cavolte!

[sqrt2]

Intanto grazie moebius per esserti dedicato al problema, perchè non avevo idee produttive su come attaccarlo(tant'è vero che l'ho postato in tdn anzichè combinatoria).
Per quanto riguarda la soluzione, l'ho letta di fretta ma direi che l'idea di fondo è giusta.
Solo una piccola correzione: volevi scrivere "Se trovo k+1 numeri consecutivi".

ps:puoi togliere la citazione dal tuo post di modo che sia leggibile a tutti? Se uno non vuole leggerlo per affrontare da solo il problema non lo guarda.

[julio14]

ps:puoi togliere la citazione dal tuo post di modo che sia leggibile a tutti? Se uno non vuole leggerlo per affrontare da solo il problema non lo guarda.

Meglio lasciarla, l'occhio potrebbe cadere anche per caso sull'intuizione giusta... e cmq per vedere basta selezionare con il mouse

[Marco]

Io ho un'altra soluzione sostanzialmente diversa di questo problema, basata sull'idea che la densità asintotica dei quadrati è zero.

Fissiamo una barretta e osserviamo la successione delle somme di coppie di palline consecutive lungo la barretta. Per costruzione tale successione è di quadrati perfetti, e dato che le palline sono in ordine strettamente crescente, anche la successione di quadrati è crescente.

Diciamo allora di aver piazzato $ N $ palline e che ci siano $ Q $ quadrati positivi minori o uguali a $ 2N $. Per la considerazione sopra, ogni barretta non può contenere più di $ Q+1 $ palline e le barrette sono $ k $, quindi $ N \leqslant k(Q+1) \leqslant k \sqrt{2N} + k $.

Questa disequazione non può valere per tutti gli $ N $ (boh, ad esempio $ N=\frac{9}{2}k^2 $ va già male...), quindi fissato $ k $, il numero di palline piazzabili è limitato. []