OliForum Matematico

E' ovvio, così usi lo stack per tenere i riporti, e quindi usi spazio aggiuntivo lineare. Si può fare senza ricorsione e in spazio costante.

Non ho capito cosa intendi per tralasciando la parte intera, ma
stando al tuo pseudocodice 999 + 001 farebbe 900.

Chiaramente ottimi in senso asintotico. In altre parole la soluzione ottima deve usare spazio (=numero di celle di memoria) aggiuntivo costante e indipendente dalla dimensione dell'input, e tempo proporzionale alla dimensione dell'input.

Notate che non è una banale trasposizione della somma di interi, perchè l'algoritmo da scuola materna richiede alla meglio spazio aggiuntivo lineare, data la particolare rappresentazione dell'input. Infatti, facendo la somma con riporto nel modo banale, dobbiamo elaborare le cifre nell'ordine dalla ...

Le cifre decimali di due interi x e y (arbitrariamente grandi) sono rappresentate tramite due liste di interi tra 0 e 9 singolarmente linkate. Vale a dire ogni nodo di ciascuna lista contiene una cifra e un puntatore alla cifra successiva (ma non alla precedente). Problema: dare un algoritmo che met...

HINT: una specie di ricerca binaria e controllo di parità

E' vero, alla fine A e B non fanno altro che colorare un particolare ipergrafo, infatti il lemma è equivalente alla soluzione.

Ma se volete esiste anche un modo elementare e diretto per farlo, che usa al più l'aritmetica modulo 2 ...

... precisazione: la comunicazione è a senso unico da A verso B: ossia il tutto si riduce ad A che invia un unico messaggio a B di lunghezza logaritmica. Non è prevista nessuna interazione da B, che può ricevere da A ma non rispondere.

Yes...

Ci sono due persone A e B, che possiedono rispettivamente due sequenze binarie x e y. Nessuno dei due conosce la sequenza posseduta dall'altro, ma si sa che x e y hanno la stessa lunghezza e differiscono in un solo bit (che è ovviamente ignoto sia ad A che a B). Dimostrare che mediante una strategia...

Ok ma questo esclude soltanto il caso in cui le regioni sono triangoli a loro volta. Cosa si può dire più in generale?

E' possibile costruire un triangolo che non può essere dissezionato in 3 regioni congruenti ?

ps: Non so se sia un problema noto o meno, ne quanto sia difficile la risposta perchè la ignoro io stesso. Avete qualche idea?

Beh, in effetti forse sono io che confondo Algebra e Combinatoria .
Al di là di questo la soluzione dovrebbe essere quella. Se volete leggerla ecco la partizione che risolve il problema:

In A tutti gli interi che hanno un numero pari di 1 nella rappresentazione binaria e in B tutti gli altri

Dimostrare che:
Per ogni k si possono partizionare gli interi da 1 a $ 2^k $ in due insiemi A e B tali che, per ogni $ 1 \leq i \leq k-1 $, le sommatorie delle potenze i-esime degli interi in A e in B sono uguali. Enjoy!

P.S.: l'ho postato qui perchè la soluzione mi sembra essenzialmente combinatoria

Ci sono N punti bianchi ed N punti neri nel piano tali che nessuna retta passa per più di 2 punti, bianchi o neri che siano. Dimostrare che comunque siano disposti i punti si possono sempre tacciare N segmenti con un estremo bianco e l'altro nero tali che nessuna coppia di segmenti si intersechi. (N...