Trova il minimo n

[pi_greco_quadro]

Sia $ A=\{p^aq^br^c\mid 0\leq a,b,c\leq 5\} $. $ p,q,r $ sono numeri primi distinti.
Trovare il più piccolo $ n $ per cui, comunque scelto un sottoinsieme di $ A $ di $ n $ elementi, esistono in esso $ x,y $ distinti tali che $ x\mid y $

[MateCa]

Peccato che questo problema sia caduto nel dimenticatoio, sembra interessante...

Dunque, innanzi tutto perchè due numeri che appartengono ad A siano divisibili è necessario che gli "esponenti" (a,b,c) di uno siano tutti minori-uguali o tutti maggiori-uguali a quelli dell'altro.
Quindi, se ho capito bene, il problema si riduce (si fa per dire ) a trovare quanti sono gli elementi del più grande sottinsieme di A che contiene solo numeri non divisibili tra loro. Detto quindi $ m $ il numero degli elementi di tale sottinsieme, $ n $ vale banalmente $ m+1 $.

[3C273]

Problema carino!
Avevo provato a farlo un po' di tempo fa, ma non ho scritto niente perchè non ho la soluzione... ho dimostrato solo che $ 28\leq n \leq37 $, ma ovviamente non è sufficiente... spero almeno che sia giusto!! Ora posto quello che ho trovato (anche se mi rendo conto che è la parte "facile") perchè mi sembra che questo problema sia stato abbandonato e vorrei "rilanciarlo"... sarei curiosa di sapere come si può andare avanti!
1) $ n\geq28 $
Chiaramente, considerando gli elementi di $ A $ per cui $ a+b+c=k $ con $ k $ fissato, la condizione richiesta non è verificata (nessuno ne divide un altro, perché affinché la somma sia costante se aumento $ a $ devo diminuire $ b $ e/o $ c $). Poichè il massimo numero di elementi di $ A $ con lo stesso $ k $ è 27 (con $ k=7 $ o $ k=8 $), si ha che $ n\geq28 $.
2) $ n\leq37 $
Principio dei cassetti: metto in relazione di equivalenza gli elementi che hanno la stessa $ b $ e la stessa $ c $ (ogni classe contiene 6 elementi al variare di $ a $, e ci sono 36 classi). Comunque scelti 2 elementi appartenenti alla stessa classe, uno divide l'altro; da cui $ n\leq37 $.
In realtà, in una maniera un po' macchinosa e brutta, ho dimostrato anche che $ n\leq36 $ (e nello stesso modo si può abbassare ancora credo, ma è veramente triste così...)

PS: se dovessi scommettere, punterei senz'altro sul 28
Ciao!

[moebius]

Anche io punterei sul 28 ma... il perchè non lo saprei giustificare decentemente.
L'unica cosa che mi è venuta è andare per diagonali...

[moebius]

Ok... lo ammetto... sono pigro ma soprattutto oramai mi sono quasi fissato...
vorrei farlo con i cassetti... solo che non trovo quali cassetti usare
Ideas?

[teppic]

vorrei farlo con i cassetti... solo che non trovo quali cassetti usare

Prova con i miei cassetti .

Costruiamo 28 sottoinsiemi di A in questo modo.

Partendo da un punto (a,b,c) di A con a+b+c=5, considero il sottoinsieme che comprende (a,b,c), (a+1,b,c), (a+1,b+1,c), (a+1,b+1,c+1), (a+2,b+1,c+1), ...
Metto nello stesso insieme anche (a,b,c-1), (a,b-1,c-1), e così via (fino a che sono dentro A).

L'insieme "serpeggiante" così ottenuto può essere costruito a partire da qualunque punto con a+b+c=5: i 28 sottoinsiemi ottenuti hanno intersezione vuota (esercizio per il lettore ) e la loro unione è tutto A.

Se due punti appartengono allo stesso serpentone, certamente le coordinate di uno sono tutte minori o uguali di quelle dell'altro.

[Edit] Notare che questa costruzione è sbagliata: come notato sotto, i sottoinsiemi sono 27 e si parte dai punti con a+b+c=7.

[3C273]

Eh sì, mi sa proprio che funziona!
(intendevi a+b+c=7, non 5, giusto? e costruisci 27 sottoinsiemi, non 28, no?)
Per dimostrare che gli insiemi sono una partizione di A basta notare che i sottoinsiemi sono costruiti aggiungendo 1 ad a, b o c a seconda che la somma (a+b+c) modulo 3 sia rispettivamente 1, 2 o 0, o analogamente togliendo 1 ad a, b o c se la somma (a+b+c) modulo 3 è rispettivamente 2, 0 o 1. Questo permette di "invertire" la costruzione, cioè tornare al "rappresentante" della classe (quello con a+b+c=7) in maniera unica a partire da qualsiasi terna.

Mi sembra che basti! Sbaglio qualcosa? (confusione a parte!!!)
Grazie teppic!

[moebius]

Si,credo anche io che debbano essere a somma 7 i rappresentanti.Lampo di genio?no,solo che così i cassetti sono abbastanza pochi da permettere di concludere!Non che per 28 non funzioni ma lo scopo era ammazzare gli insiemi da 28 e non quelli da 29 Grazie!

[teppic]

Eh sì, mi sa proprio che funziona!

In realtà, come avrai capito non ho controllato molto bene, soprattutto i conti. Se anche a voi sembra che funzioni, funzionerà!

(intendevi a+b+c=7, non 5, giusto? e costruisci 27 sottoinsiemi, non 28, no?)

Non ti dico che serie di considerazioni sbagliate stavo facendo... comunque sì. La soluzione dovrebbe venire con a+b+c=7 oppure 8. Le combinazioni buone in entrambi i casi sono 27, qunidi i sottoinsiemi pure.

Questo permette di "invertire" la costruzione, cioè tornare al "rappresentante" della classe (quello con a+b+c=7) in maniera unica a partire da qualsiasi terna.

Mi sembra impeccabile!

[3C273]

PS: se dovessi scommettere, punterei senz'altro sul 28

Anche io punterei sul 28

@$ \pi^{2} $: ...ora che l'abbiamo dimostrato devi offrirci da bere!!!

[moebius]

@$ \pi^{2} $: ...ora che l'abbiamo dimostrato devi offrirci da bere!!!

Si però poi noi dovremmo offrire da bere a teppic... Ok, proposta: ci accordiamo su un drink comune (suggerisco cuba) e chiediamo a teppic cosa prende. Dopo di che $ \pi^2 $ paga. E speriamo che il bicchiere per il cuba sia largoooooo...

[teppic]

Buoni, se no qualche moderatore (tipo io) sposta il 3d nella... birreria

Io comunque prendo un bicchiere di Picolit.