Divisibilità e riempimento con blocchi uniformi ed equispaziati
Mi sono riproposto di analizzare il seguente semplice problema, apparentemente elementare.
Si tratta di riempire uno spazio unidimensionale di lunghezza di D unità (tutte le misure sono intere) con N "blocchi" di lunghezza K da scegliere opportunamente, messi uno di seguito all'altro, tali che la distanza tra l'inizio del primo e la fine dell'ultimo sia esattamente N e tale che i blocchi siano separati da uno spazio di esattamente 1 unità.
Pertanto, dati N blocchi lunghi K e separati da un'unità lo spazio occupato sarà:
$ D=(N-1) + N*K $
Il problema consiste, data la lunghezza totale D, stabilire quali combinazioni di N e K siano effettivamente possibili.
Trovare la/e soluzione/i con un metodo "brute force" è elementare, è sufficiente risolvere per N e provare tutti i valori di K da 1 a D (o, viceversa, risolvere per K e provare tutti gli N)
Qualcuno si è occupato i questo o problemi simili?
Si può fare qualcosa di più intelligente della forza bruta? Mi sapreste indicare eventualmente qualche link od, eventualmente, con quali termini tecnici è conosciuto in letteratura il problema?
Grazie in anticipo
Si tratta di riempire uno spazio unidimensionale di lunghezza di D unità (tutte le misure sono intere) con N "blocchi" di lunghezza K da scegliere opportunamente, messi uno di seguito all'altro, tali che la distanza tra l'inizio del primo e la fine dell'ultimo sia esattamente N e tale che i blocchi siano separati da uno spazio di esattamente 1 unità.
Pertanto, dati N blocchi lunghi K e separati da un'unità lo spazio occupato sarà:
$ D=(N-1) + N*K $
Il problema consiste, data la lunghezza totale D, stabilire quali combinazioni di N e K siano effettivamente possibili.
Trovare la/e soluzione/i con un metodo "brute force" è elementare, è sufficiente risolvere per N e provare tutti i valori di K da 1 a D (o, viceversa, risolvere per K e provare tutti gli N)
Qualcuno si è occupato i questo o problemi simili?
Si può fare qualcosa di più intelligente della forza bruta? Mi sapreste indicare eventualmente qualche link od, eventualmente, con quali termini tecnici è conosciuto in letteratura il problema?
Grazie in anticipo
Risposte
"ettore_galli":
$ D=(N-1) + N*K $
Da cui $ N\cdot (K+1)=D+1 $ e da qui si hanno facilmente le soluzioni...
Si ma mi mi chiedevo se dato D è possibile trovare tutte le coppie di n e k intere più facilmente che con tentativi multipli.
Le mie soluzioni erano le seguenti:
$K = (D-N +1)/N$
oppure, ovviamente
$N = (D-N +1)/N$
Il che mi costringe comunque a tentativi multipli...
Con la tua relazione come posso arrivare direttamente ai soli risultati interi?
Le mie soluzioni erano le seguenti:
$K = (D-N +1)/N$
oppure, ovviamente
$N = (D-N +1)/N$
Il che mi costringe comunque a tentativi multipli...
Con la tua relazione come posso arrivare direttamente ai soli risultati interi?
Nella formula che ti ho scritto, il secondo membro è uguale a $D+1$, che è fissato e lo conosci. Siccome sia $N$ che $K+1$ e anche $D+1$ sono interi, $K+1$ deve essere per forza un divisore di $D+1$ maggiore di $1$. Così ti trovi tutti i possibili valori di $K+1$ (quindi tutti i valori di $K$), ed il valore di $N$ corrispondente si ottiene facendo $\frac{D+1}{K+1}$, che è sicuramente intero e positivo.
"milizia96":
... Siccome sia $ N $ che $ K+1 $ e anche $ D+1 $ sono interi, $ K+1 $ deve essere per forza un divisore di $ D+1 $ maggiore di $ 1 $. ...
Il problema è esattamente questo, $N$ non è, ma deve essere intero il che mi costringe - salvo, lo ripeto, soluzioni migliori - ad andare per tentativi...
Forse con un esempio la cosa risulta più facile.
Dia $D=99$; Se pongo $N=2$ deduco facilmente che $K=49$, se provo $K=47$ oppure $K=50$ verifico che non trovo un corrispondente valore di $D$ intero;
Le altre soluzioni sono:
$N= 1; K=99$
$N= 2; K=49$
$N = 4; K=24$
$N = 5; K=19$
$N=10; K=9$
$N=20; K=4$
$N=25; K=3$
$N=50; K=1$
Se, per esempio, provo $N=3$ è immediato osservare che $K=32,3$, soluzione non accettabile in quanto non intera.
Posso arrivare alle soluzioni riportate sopra facendo passare i $K$ e deducendo gli $N$ e tenendo solo i valori interi ma non riesco ad individuare un metodo - se c'è - per arrivare "direttamente" ai $K$ o agli $N$ "buoni"
Qualche idea?...
Forse prima non mi sono spiegato bene...
Risolviamo il tuo caso $D=99$.
Come ho detto, $K+1$ deve essere un divisore di $D+1$, cioè un divisore di $100$.
I divisori di $100$ sono: $1,2,4,5,10,20,25,50,100$
Quindi $K+1$ può essere uguale a $0,1,3,4,9,19,24,49,99$
Ma si esclude $0$ perché abbiamo detto che $K$ è positivo.
Quindi le soluzioni sono
$K=1, \qquad N=50$
$K=3, \qquad N=25$
$K=4, \qquad N=20$
$K=9, \qquad N=10$
$K=19, \qquad N=5$
$K=24, \qquad N=4$
$K=49, \qquad N=2$
$K=99, \qquad N=1$
Dove ogni volta la $N$ si ottiene facendo $\frac{D+1}{K+1}$ cioè $\frac{100}{K+1}$
Risolviamo il tuo caso $D=99$.
Come ho detto, $K+1$ deve essere un divisore di $D+1$, cioè un divisore di $100$.
I divisori di $100$ sono: $1,2,4,5,10,20,25,50,100$
Quindi $K+1$ può essere uguale a $0,1,3,4,9,19,24,49,99$
Ma si esclude $0$ perché abbiamo detto che $K$ è positivo.
Quindi le soluzioni sono
$K=1, \qquad N=50$
$K=3, \qquad N=25$
$K=4, \qquad N=20$
$K=9, \qquad N=10$
$K=19, \qquad N=5$
$K=24, \qquad N=4$
$K=49, \qquad N=2$
$K=99, \qquad N=1$
Dove ogni volta la $N$ si ottiene facendo $\frac{D+1}{K+1}$ cioè $\frac{100}{K+1}$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo