Problemi gara e a squadre

[Loth]

[...] forse è il 17 che porta male e non andava scelto come jolly

Sagge parole... Fermat docet!

[Marco]

Piever: le pozioni vanno unite a terzine incompatibili fra loro. Ogni elemento della terzina si può combinare con i 33 esterni alla terzina quindi si ha: 36*33/2=594

Non so quanti se ne siano accorti, ma nel problema delle pozioni c'era una soluzione quasi ottimale molto simpatica, in cui un ingrediente è inutile e le pozioni che non lo contengono sono tutte buone (un grafo bipartito (1,35), per capirci). Le "coppie cattive" sono 35 (contro le 36 della soluzione ottimale). Notate anche che se gli ingredienti fossero stati 37, la soluzione con un ingrediente inutile sarebbe stata ottimale ex-aequo con quella delle terzine....

[14.19]

Non capisco perchè un elemento dovesse per forza essere incompatibile con altri 2 e non con un altro...

[piever]

Piever: le pozioni vanno unite a terzine incompatibili fra loro. Ogni elemento della terzina si può combinare con i 33 esterni alla terzina quindi si ha: 36*33/2=594

Non so quanti se ne siano accorti, ma nel problema delle pozioni c'era una soluzione quasi ottimale molto simpatica, in cui un ingrediente è inutile e le pozioni che non lo contengono sono tutte buone (un grafo bipartito (1,35), per capirci). Le "coppie cattive" sono 35 (contro le 36 della soluzione ottimale). Notate anche che se gli ingredienti fossero stati 37, la soluzione con un ingrediente inutile sarebbe stata ottimale ex-aequo con quella delle terzine....

Geniale!!!

@ 14.19: Non ci possono essere 4 elementi tutti incompatibili fra loro (sarebbero due coppie) ma ci possono essere delle terzine incompatibili fra loro in modo da diminuire il numero di possibilità totali. Non mi so spiegare, spero che tu abbia capito.

[14.19]

Capito!!! Grazie!

[giorgiosironi]

Come si risolve il 4 pubblico?
E' il minimo di $ \frac{4a^3}b + \frac{b+1} a $ con a e b reali positivi.

Il metodo più veloce per risolvere questo è derivare rispetto ad a e a b e porre uguali a zero entrambe le funzioni ottenute. Così trovi subito un sistemino dove a=b=1/2

[teppic]

Un altro suggerimento, anche se non aggiunge tantissimo. (Se non che l'autore del problema lo ha pensato così )

Le configurazioni diventano più comprensibili se si passa al grafo complementare, ovvero se si immaginano gli ingredienti come punti e di connettere le coppie incompatibili.

Le regole di Hermita, lette su questo grafo, diventano che se tra A e B esiste una connessione e tra C e D ne esiste un'altra, allora le due coppie devono far parte di due gruppi tra loro non connessi.

A questo punto è facile vedere che nessun gruppo di punti connessi può avere più di tre elementi. Allora, visto che per risolvere il problema bisogna cercare la configurazione con più connessioni, basta dividere i 36 ingredienti in 12 3-grafi completi (triangoli) tra loro sconnessi e contare quante sono le connessioni ($ \small3\cdot12 $) rispetto a tutte le coppie di ingredienti $ \binom{36}2 $.

[Boll]

Come si risolve il 4 pubblico?
E' il minimo di $ \frac{4a^3}b + \frac{b+1} a $ con a e b reali positivi.

Il metodo più veloce per risolvere questo è derivare rispetto ad a e a b e porre uguali a zero entrambe le funzioni ottenute. Così trovi subito un sistemino dove a=b=1/2

Bah, buh, bah, è una semplice Am-Gm pesata
$ $ \frac{4a^3}{b}+\frac{b}{a}+\frac{1}{2a}+\frac{1}{2a}\ge 4\sqrt[4]{ \frac{4a^3}{b}\cdot \frac{b}{a}\cdot \frac{1}{2a}\cdot \frac{1}{2a}}=4 $

EDIT: Febb aveva ragione

[Marco]

teppic: A questo punto è facile vedere che nessun gruppo di punti connessi può avere più di tre elementi.

Teppic, Teppic... Questo è vero nel caso 36, ma non è né così facile, né così ovvio; tant'è vero che nel caso di ingredienti non divisibili per 3 è falso.

[enomis_costa88]

Come si risolve il 4 pubblico?
E' il minimo di $ \frac{4a^3}b + \frac{b+1} a $ con a e b reali positivi.

Il metodo più veloce per risolvere questo è derivare rispetto ad a e a b e porre uguali a zero entrambe le funzioni ottenute. Così trovi subito un sistemino dove a=b=1/2

già noi abbiamo fatto così ma non è un bel metodo, in questo caso era veloce ma spesso è lungo e calcoloso
Mi pare che in teoria una volta imposto il gradiente di una funzione uguale al vettore nullo si dovrebbe anche cercare eventuali massimi/minimi sul bordo (un po' come quando si usa lagrange..) oppure verificare che non ci sono massimi o minimi sul bordo (in questo caso ci interessavano solo i minimi).

Bella la soluzione di Frengo

[thematrix]

Bah, buh, bah, è una semplice Am-Gm pesata
$ $ \frac{4a^3}{b}+\frac{b}{2a}+\frac{b}{2a}+\frac{1}{a}\ge 4\sqrt[4]{ \frac{4a^3}{b}\cdot \frac{b}{2a}\cdot \frac{b}{2a}\cdot \frac{1}{a}}=4 $

ehm,sbaglio o c'è una b di troppo al numeratore?

[Fede_Coach]

Pubblico 14, "La seconda prova". Trovare $ 4\cdot 7^{23}+3^{11} \mod 101 $.

Qual è il trucco????

La soluzione più rapida (e carina) che ho visto finora è questa (by Tasin):

$ 2^{9} = 7 \mod 101 $ quindi, sostituendo, si ottiene $ 2^{11} \cdot 7^{22} +3^{11} \mod 101 $ che si può scrivere come
$ (2 \cdot 7^{2} +3) \cdot (...) = 101 \cdot (...) $

[davigall]

Per risolvere il 14 della del pubblico ho tratto inspirazione dal problema 5 delle nazionali del 2002.

La soluzione stava nel applicare più volte il binomio di Newton alle adeguate potenze di 7 e di 3 in modo da diminuire i calcoli.

[edriv]

Allora era un bel problema, quello.
Nel senso che non basta ripassare a mente tutti i teoremi di teoria dei numeri chi si conosce (tipo Fermat), ma serve ingegnarsi...

[piever]

Ok, ora ho capito!
Grazie Boll