Exos sympas MP(*)

[Artix]

SPOILER:

Ma méthode (sûrement pas optimale) pour le fil de bonbons.
Prenons par exemple le fil : 12232423112635231254
Alors on y va couleur par couleur en considérant successivement les bonbons qui n'ont pas de voisins de même couleur, tant qu'il y a des bonbons "solitaires".
Par exemple ici, pour la couleur 1, il y en a deux.
On applique alors récursivement l'algorithme aux différents cas, dans l'exemple : soit le premier 1 est gâché. Soit le premier 1 est mangé avec le "11", soit tout les 1 sont mangés tous ensemble. Dans le premier cas on applique l'algo au fil privé du premier 1, dans le deuxième cas à 2232423 et 2635231254 et dans le troisième cas à 2232423 263523 et 254. (Biensûr on regroupe les différents cas à la fin pour voir quel est la meilleure solution.)
Puis quand il n'y a plus de bonbons solitaires pour un couleur, on supprime tout les bonbons de la couleur (on ne gaspille pas, pas d'inquiétude !), puis on passe à la couleur suivante. (On compte évidemment à chaque fois le nombre de bonbons gâchés).

C'est pas mal, mais je comprends pas quels cas tu distingues exactement en général. Il faut que ton algo soit le plus exhaustif possible
Essaie de faire marcher ce truc, et de le rendre efficace. Puis généralise

Montrer que dans tout groupe de 50 personnes, il y en a au moins deux qui ont un nombre pair de connaissances communes (la relation « se connaître » est symétrique et on ne se connaît jamais soi-même).

Une méthode un peu tordue...

SPOILER:

On appelle G le graphe.
Pour un noeud k de G, on note v(k) l'ensemble des voisins de k, et n(k) = | v(k) |.
On note A-B si deux noeuds A et B sont reliés.
Raisonnons par l'absurde. On remarque que pour tout noeud k du graphe, deg k >= 2 sinon c'est gagné.
Soit k un noeud du graphe. Pour y dans v(k), le degré de y dans le graphe induit par v(k) est impair, par hypothèse. Donc n(k)=somme de degré des y = 2nbAretes est pair.
Ainsi tous les noeuds du graphe ont un degré pair.
En particulier, tous les noeuds de v(k) ont un degré pair. Or ils sont reliés à k et à un nombre impair de noeuds de v(k). Donc à un nombre pair de noeuds dans G\v(k). Donc somme i dans G\v(k) des v(i) inter v(k) est pair, or pour tout i dans G\v(k), v(i) inter v(k) impair. Donc | G\v(k) | pair.

Mais 50 = | G | = | v(k) | + | G\v(k) | + 1 impair, absurde.

[symétrie]

Quelle est la longueur minimale d'une suite d'entiers entre 0 et 9 dans laquelle apparaît consécutivement tout mot de longueur 4 sur l'alphabet {0, …, 9} ?

[symétrie]

Ouais… Mais c'est plus drôle quand on ne connaît pas.

[symétrie]

Ça devient assez naturel avec un peu de boulot et un peu de culture combinatoire dont je pense qu'on peut l'acquérir sans l'avoir avant d'aborder ce problème, en faisant bon usage de Wikipédia. Mais oui c'est pas évident (et pourtant c'est un problème somme toute assez naturel). Pour information, c'était un des problèmes posés lors de la préparation française aux diverses olympiades pour élèves de lycée (on avait un moins pour résoudre, rédiger, et renvoyer 6 problèmes, celui-là était l'avant-dernier, sachant que les problèmes étaient rangés par ordre croissant de difficulté).

[np*]

Exo 1 : Combien y a-t-il de 0 à la fin de n! ?

SPOILER:

Code : Tout sélectionner

let legendre n p =
  let rec aux acc i =
    let e = n / (int_of_float (p ** i)) in
    if e = 0 then acc
    else aux (acc + e) (i+.1.)
  in aux 0 1.
  
let _ =
  let n = Scanf.scanf " %d" (fun x -> x) in
  let v_5 = legendre n 5. in
  print_int v_5

Je préfère :

SPOILER:

Code : Tout sélectionner

let legendre n p =
    let rec aux acc r =
        let r = r / p in
        if r = 0 then acc else aux (acc + r) r
    in
    aux 0 n
    
let nb_trailing_zeros_fact n = legendre n 5

Oui ce n'est qu'une tentative de réveiller ce sujet pour ceux qui préparent les oraux d'info aux ENS

[Bidoof]

.

[LeCaRiBoU]

Tiré de problèmes d'ACM, il est vraiment classe à résoudre :

Je choisis un string de 2k < 1000 bits que je garde pour moi. Vous allez alors me faire des requêtes, je vous répondrai quelque chose selon la requête, et on continue jusqu'à ce que vous ayez la bonne réponse, sachant que vous avez le droit de vous servir de mes réponses aux requêtes précédentes. Une requête consiste à me proposer un string de 2k bits, et je vous réponds alors par l'une de ces trois réponses :
- Le string que vous avez proposé est le bon => GG, le jeu est fini et vous avez gagné.
- Le string que vous avez proposé a exactement k bits qui différent de mon string.
- Nous ne sommes dans aucun des deux cas précédents.

Trouver un algo pour trouver le string initial en moins de 2k + 500 requêtes.

Petits spoilers pour vous éviter d'être bloqués :

Le premier spoile pas grand chose et j'aurais peut-être du le mettre dans le problème initial :

SPOILER:

J'attends de votre algo qu'il y arrive avec trèèèèèèèèèèèèès forte probabilité

Le deuxième spoile un peu la solution :

SPOILER:

Si vous faites la somme des résultats des lancers de deux dés, que pouvez-vous dire de la proba qu'elle soit de 7 par rapport à celle qu'elle soit de 2

Avec le troisième, la solution devient évidente :

SPOILER:

Si vous avez un string à distance k du string initial, comment finir ?

[Xavpoucaz]

Pour k < 5, on peut trouver à coup sûr en moins de 2^(2k) < 2k+500 requêtes sans trop réfléchir !

[gchacha]

Un petit théorème classique de mise en bouche : "On considère un mot $ u $ de période $ a $ et $ b $ et de longueur égale à $ a+b-pgcd(a,b) $. Montrer que c'est la plus petite longueur possible pour que $ pgcd(a,b) $ soit une longueur de $ u $."