Ripetitori

Giochini matematici elementari ma non olimpici.
Rispondi
Avatar utente
Quarantadue
Messaggi: 28
Iscritto il: 13 feb 2009, 18:34

Ripetitori

Messaggio da Quarantadue »

Soluzione con dimostrazione?

Su una linea di trasmissione dati sono inseriti in serie un certo numero (inferiore a 1000) di ripetitori, tutti identici tra loro. Si scopre che, a causa di un gravissimo errore di progettazione, i ripetitori effettuano un ben preciso rimescolamento nell'ordine degli 8 bit di ogni byte in transito.
Sapendo questo, e pur non conoscendo il modo con cui i bit vengono permutati, un matematico afferma che la linea funzionerà perfettamente. Quanti sono i ripetitori?
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

840?
la dimostrazione a voi
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Bonus: si vuole progettare una linea di trasmissione con dei ripetitori in serie, e perché la linea funzioni c'è bisogno di almeno un ripetitore. Si sa che i ripetitori prodotti da una certa ditta permutano gli 8 bit di ogni byte in un modo fissato, ma si scoprirà in quale modo solo dopo che i ripetitori saranno stati ordinati e consegnati. Quanti ripetitori bisogna ordinare a questa ditta, come minimo, per essere certi di poter costruire una linea funzionante?

Altro bonus: generalizzare per quanto possibile a n bit anziché 8.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo »

A me viene
$ lcm\left( \; \left(\begin{array}{c} 8 \\ 1 \end{array}\right)\; ,\; \left(\begin{array}{c} 8 \\ 2 \end{array}\right)\; ,\; \left(\begin{array}{c} 8 \\ 3 \end{array}\right)\; ,\; \left(\begin{array}{c} 8 \\ 4 \end{array}\right)\; \right) $
cioè 280
non capisco dove mi perdo un fattore 3,del resto si capisce che 840 è quella giusta..ma non capisco dove perdo un 3...
trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo »

nessuno me lo sa dire?
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

Il problema non è che ti perdi un fattore 3. Il problema è che probabilmente è sbagliato il conto che hai fatto. Non riesco a capire che ragionamento hai fatto per arrivare a quel minimo comune multiplo, perché non posti la tua soluzione? Altrimenti è difficile capire dove stia l'errore.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo »

Ah in effetti non avevo considerato la possibilità di aver sbagliato completamente ragionamento XD
Comunque avevo pensato questo
intanto ogni bit può assumere 2 valori : 0 ed 1 (credo)
ed ogni byte dovrebbe essere quindi una sequenza di 8 caselle che possono essere riempite o da 0 o da 1

se il byte è formato da soli 1 (o soli 0 non cambia la cosa)
allora qualunque rimescolamento va bene
se il byte è formato da due 1 e sei 0
allora posso supporre che almeno uno dei due 1 ad ogni passaggio dal ripetitore cambi posizione e ci sono
$ \left(\begin{array}{c} 8 \\ 2 \end{array}\right) $ modi diversi per combinarli,quindi affinché l'informazione si conservi,il numero dei ripetitori dovrebbe essere un mutliplo di quel binomiale

e così via sono arrivato a
$ \left(\begin{array}{c} 8 \\ 4 \end{array}\right) $
e ne ho fatto il minimo comune multiplo...
la cosa grave è che non trovo l'errore :oops: :oops: :oops:
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

trugruo ha scritto: allora posso supporre che almeno uno dei due 1 ad ogni passaggio dal ripetitore cambi posizione e ci sono
$ \left(\begin{array}{c} 8 \\ 2 \end{array}\right) $ modi diversi per combinarli,quindi affinché l'informazione si conservi,il numero dei ripetitori dovrebbe essere un mutliplo di quel binomiale
Beh, questo però dipende dalla permutazione, no? A seconda di come scambi i bit, il numero di ripetitori che ti serve per tornare alla posizione iniziale cambia. Non è che i tuoi due bit 1 devono per forza fare il giro di tutte le posizioni possibili...

Prova a pensare in termini del rimescolamento che viene effettuato, piuttosto che della posizione iniziale dei bit.
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
trugruo
Messaggi: 192
Iscritto il: 31 ago 2009, 15:04

Messaggio da trugruo »

Nonno Bassotto ha scritto: Beh, questo però dipende dalla permutazione, no? A seconda di come scambi i bit, il numero di ripetitori che ti serve per tornare alla posizione iniziale cambia. Non è che i tuoi due bit 1 devono per forza fare il giro di tutte le posizioni possibili...
Effettivamente è vero...è la mia voglia che tutto si possa semplificare immediatamente a farmi partorire questi obbrobri...
Avatar utente
Nonno Bassotto
Site Admin
Messaggi: 970
Iscritto il: 14 mag 2006, 17:51
Località: Paris
Contatta:

Messaggio da Nonno Bassotto »

Beh, adesso non ti buttare giù così... :wink:
The best argument against democracy is a five-minute conversation with the average voter. - Winston Churchill
Rispondi