Bonjour à tous,

Je suis actuellement confronté à un problème que je ne suis pas parvenu à résoudre, pourtant je suis persuadé qu'il s'agit d'une problématique connue des mathématiciens (je suis chercheur en informatique).

Voici le problème.
Je dispose d'un vecteur $x=(x_1,\dots,x_n)$ à valeurs entières (entiers relatifs), non nécessairement distinctes.
Soit $s$ la somme de $k$ valeurs du vecteurs, éventuellement les mêmes ($k$ est fixé), prises aléatoirement.
Par exemple, pour $k = 2$, $s = x_1 + x_1$ est une possibilité. $k$ peut être supérieur à $n$.
En gros, on tire $k$ fois une valeur du vecteur, avec relance, et on les somme.

Plus précisément, soit $y=(y_1,\dots,y_k)$ un vecteur d'indices aléatoire, avec $y_i \in \{1,\dots,n\}$.
A partir de $x$ et en fonction de $y$, on peut générer une somme $s = x_y_1 + x_y_2 + \dots + x_y_k$.

Ma question est la suivante : étant donné un vecteur $x$, quelle est la probabilité qu'une somme $s$ obtenue à partir d'un vecteur $y$ aléatoire (mais de taille connue) soit supérieure à une constante donnée $c$ ?

Je ne cherche pas une réponse théorique, mais une solution pouvant être mise en pratique par un algorithme polynomial en temps et en espace.

Par exemple, si $x=(-1, -1, 5)$ et $k=4$, je somme 4 valeurs, chacune étant soit -1, soit 5, sachant que -1 a deux fois plus de chances d'apparaitre que 5.
Après une simple simulation sur les $3^4 = 81$ cas possibles, cela nous donne les probabilités suivantes :
$p(s=-4) = 16/81$
$p(s=2) = 32/81$
$p(s=8) = 24/81$
$p(s=14) = 8/81$
$p(s=20) = 1/81$
Donc, par exemple, $p(s>0) = 65/81$.
Comment arriver à ce résultat sans simulation ?

Je remercie les courageux qui m'auront lu jusqu'au bout.
Si vous êtes certains qu'un tel calcul est impossible par un algorithme polynomial (ce qui était ma première conviction), je suis également preneur, même si je serais déçu...

Bonjour,

pendant ces derniers jours a eu lieu la compétition "International Mathematics Competition", les participants sont des étudiants de L1-L2-L3-M1 de différentes Universités (et grandes écoles). Cinq étudiants ont représenté l'Ecole Polytechnique : Che-Yu Liu, Yu Liu, Laurent Deproit, Rafael de Rezende et Chaojun Wang. Les épreuves se déroulent sur deux jours, 5 heures par composition. Les sujets de cette année sont la :
[attachment 16584 IMC2010Day1.pdf]
[attachment 16585 IMC2010Day2.pdf]

Bon, je n'ai pas réussi à retrouver les fils anciens où j'ai déjà abordé ce sujet donc j'en ouvre un dans lequel "je me dois" de dire ce que d'autres m'ont dit.

Dans le passé, il m'est arrivé de déclarer ici que la plupart des physiciens maintenant reconnaissent "les preuves" MQ=>MP (axiomes de la mécanique quantique => existence de tout plein de mondes parallèles*****).

Même si ce qu'il y a après le implique est exprimé avec des mots "tarte à la crème", je trouve honnête de l'exprimer ainsi car je pense que l'état scientifique présent met la charge de la preuve dans le camp adverse.

En ce moment il y a un symposium de physique où moult exposés spéculatifs*** (ou pour présenter l'état d'avancement de certains travaux) ont cours. Quand je peux j'essaie de demander aux uns et aux autres leur position (ce n'est jamais très facile, direct leurs défenses psychologiques se mettent en place).

*** avec de vrais physiciens renommés, dont Penrose (prix Nobel?), Aspect (prix Nobel) et Zeilinger (prix Nobel?)


Aujourd'hui, j'ai pu recueillir une position sans ambiguité de l'un des organisateurs. Donc, pour la reproduire, que ce soit clair, je précise comment j'ai posé la question et la manière dont je "protocole" que quelqu'un est dans le camp "oui", ou dans le camp "non" ou dans le camp "je ne me prononce pas".

La découverte de la décohérence a simplifié la question. En effet, une des propriétés du produit tensoriel est le fait que ça passe aux multiplications (les produits scalaires se multiplient:

($a_1$ tenseur $a_2$ tenseur ... $a_n$) scalaire ($b_1$ tenseur $b_2$ tenseur ... $b_n$) = $(a_1|b_1)$ fois $(a_2|b_2)$ fois ... $(a_n|b_n)$)

Du coup, même si $a_i$ n'est pas trop orthogonal à $b_i$, la multiplication de beaucoup (en disant que ce sont des nombres dans $[0,1]$ ) va donner un nombre proche de 0 et faire apparaitre l'état "produit tensoriel des $a_i$" comme apparemment presque orthogonal à l'état "produit tensoriel des $b_i$"

Il s'ensuit que les calculs quantiques sur de gros objets convergent vers des calculs de probabilités classiques (on dit que les interférences disparaissent)

En terme de matrices, elles deviennent presque diagonales.

Si on s'arrêtent là, les MP existent, point à la ligne, aucun physicien ne peut le contester (c'est une Lapalissade, pour faire court, un monde unique ce serait si en plus il n'y avait qu'un seule nombre non nul sur la diagonale)

La décohérence, qui pour la vox populi pouvait apparaitre comme "résolvant" le problème de la mesure** en le faisant apparaitre comme une illusion est en fait assez vicieuse car bien au contraire si on présente les choses ainsi, elle le "résout bien", mais implique (même pas par théorème, mais par "Lapalissade") les MP. Dès lors, les "anti-MP" "se devaient" de ne pas la considérer comme "résolvant" le problème de la mesure**

Alors le physicien (sérieux et de renom) avec qui j'ai parlé a:

1) a reconnu l'utilité de la décohérence et la "résolution partielle par la décohérence "du paradoxe" de la mesure

2) Pense que des progrès ultérieurs conduiront à "trouver" pourquoi en fait il ne reste qu'un seul élément non nul sur la diagonale.

Voilà sa position, qui a le mérite de la clarté.

** réduction du paquet d'onde, le fait que "le chat n'apparait pas superposé mort + vivant" (le problème du chat est un problème où la matrice est déjà diagonale).

Protocole interview :

dire "on garde la diagonale" = "on est dans le camp "oui pour les MP"

dire "un jour quelqu'un découvrira que un seul élément de la diagonale in fine reste non nul" = on est dans le camp "non"

on peut ne pas se prononcer.

Remarque: les anti-MP sont anti "les axiomes de la MQ resteront tels quels évidemment, ça ne contredit pas *****

Je propose que dans ce fil, on signale toutes les interventions du déterminant en maths. Ca me parait un outil encore mystérieux (pour moi) que certains maitrisent fort bien ici, donc possibilité de mutualisation.

Voilà en quoi il m'a interpellé récemment dans le forum:

1) il permet à peu de frais de montrer que sur un anneau quelconque (commutatif) $A$ et pour toute matrice carrée $M$, il existe un vecteur $v$ non nul tel que $Mv = (0,0,0,...r)$ où $r$ est soit $0$, soit un élément régulier de $A$. Je n'ai toujours pas trouvé de preuve "logique" de ce phénomène.

2) il intervient dans la théorie des formes différentielles qui trouvent ses heures de gloire dans une application spectaculaire qui consiste à prouver en 3 lignes le théorème de Brouwer à coup de formule de Stokes

3) Il permet d'inverser uniformément les matrices à coup de "transposée de la comatrice"

4) Il permet de prouver et trouver que l'ensemble des $f(v_1,...,v_n)$ où $f$ parcourt l'ensemble des formes alternées adéquates, est un idéal principal dans "les bons" cas.

Je crois qu'il intervient aussi dans pas mal de questions sur le dérivées (Wronskien, etc) auquel je ne connais rien

5) Il me semble qu'il permet de prouver en quelques lignes que si un module est de type fini (anneau commutatif QUELCONQUE), alors toute surjection linéaire est injective.

6) Il offre un accès uniforme via le théorème de Cayley Hamilton au fait que la famille des $M^n$ est liée (module libre de type fini sur anneau quelconque)

Ca fait pas mal de choses pour un outil calculatoire...

Une liste me paraitrait intéressante.

Bonjour,
Dans "L'apologie d'un mathématicien" (p. 116), Hardy cite cette égalité de Ramanujan :
$$\int_0^{+\infty}x^{s-1}[\phi(0)-x\phi(1)+x^2 \phi(2)+...]{\rm d}x=\frac{\pi\phi(-s)}{\sin\pi s}$$
Comment faut-il la comprendre ? La fonction $\phi$ est-elle une fonction-test au sens de la théorie des distributions ? Les intégrales sont-elles des fonctionnelles régularisant à la Guelfand et Chilov chaque intégrale manifestement divergente ?
Merci d'avance pour toute idée.

Bonjour,

le 7 et 8 Juillet prochain auront lieu à Astana (Kazakhstan) les Olympiades Internationales de Mathématiques. Un fait très marquant ces dernières années c'est l'age des candidats, on voit de plus en plus de très jeunes ados prendre part à cette grande compétition. Cette année, il faut suivre les noms suivants :

$\bullet$ Byron Thonatiu Escobar Benitez, age : 13 ans, pays : Salvador
$\bullet$ Alex Song, age : 13 ans, pays : Canada
$\bullet$ Raul Arturo Chavez Sarmiento, age : 12 ans, pays : Pérou. Il a gagné une médaille de Bronze à 11 ans.
$\bullet$ Omer Cerrahoglu, age : 15 ans, pays : Roumanie. Il a gagné une médaille d'or à 14 ans.
$\bullet$ Jeck Lim, age : 14 ans, pays : Singapour. Il a gagné une médaille de Bronze à 13 ans.
$\bullet$ Nipun Pitimanaaree, age : 15 ans, pays : Thaïlande. Il a gagné une médaille d'argent à 14 ans.
$\bullet$ Ufuk Kanat, age : 15 ans, pays : Turquie. Il a gagné une médaille d'argent à 14 ans.
$\bullet$ Melih Ucer, age : 17 ans, pays : Turquie. Il a gagné une médaille d'argent à 14 ans, une médaille d'or à 15 ans et une médaille d'argent à 16 ans.
$\bullet$ Jean-François Martin, age : 16 ans, pays : France. Il a gagné deux médailles d'argent à 14 et 15 ans.
$\bullet$ Lisa Sauermann, age : 17 ans, pays : Allemagne. Elle a gagné une médaille d'argent à 14 ans, et deux médailles d'or à 15 et 16 ans respectivement.
$\bullet$ Evan O'Dorney, age : 16 ans, pays : Etats-Unis. Il a gagné deux médailles d'argent à 14 et 15 ans.
$\bullet$ Teodor Von Burg, age : 17 ans, pays : Serbie. Il a gagné une médaille de Bronze à 14 ans, une médaille d'argent à 15 ans, et une médaille d'or à 16 ans.

Bonjour,

Je suis élève en Spé, et je réfléchis sur un exo trouvé dans des annales.

On considère la fonction $f_{n} : x \geq 0 \mapsto x+\frac{x^{2}}{2}+\ldots+\frac{x^{n}}{n}$.

On s'intéresse à l'équation $f_{n}(x)=1$ d'inconnue $x$. J'ai prouvé que cette équation possédait une unique solution sur R+, et que cette solution $x_{n}$ appartient à $[0,1]$. La suite $(x_{n})$ est décroissante et minorée par $0$, donc, converge.

Pour trouver sa limite, il y avait une indication : prouver que $f_{n}(x) \geq -\ln(1-x) + \frac{x^{n}}{x-1}$ pour tout $x \in [0,1[$. J'ai montré cette inégalité, mais elle me permet seulement de conclure que la limite de $(x_{n})$ est inférieure à 1-1/e...

Quelqu'un peut-il m'aider à conclure ? Que vaut cette limite ?

Merci d'avance,

Allumette

Bonjour,

j'aimerais savoir d'où vient la notation $l$ pour désigner certains nombres premiers (j'ai entendu parler de modules de Tate d'indice $l$, de cohomologie $l$-adique...)

Merci d'avance.

PS : je n'arrive pas à écrire ledit $l$ en LaTeX, pour info il est identique à celui de l'écriture cursive manuscrite.

Pour ne pas polluer un autre fil, j'en crée un.

Il me semble que cette question est importante: rappelons la forme que prend un calcul pour une personne extérieure.

C'est un imbroglio de petits signes, en grand nombre, dont seuls les initiés peuvent (et encore même eux galèrent) accéder au "sens" qui se cacherait derrière. En général ils sont nécessaires, mais restent un outil pour la science. Il n'y a pas de théorème profond qui puisse se targuer de n'exister que grace exclusivement à un calcul.

Par ailleurs, la correpondance de Curry Howard pointe assez bien le problème que les calculs posent en ce que le signe "=" mine de rien n'est sincèrement fondé qu'au second ordre:

$a=b$ signifie $\forall X: X(a)\to X(b)$

En particulier, quand il s'est agi de réaliser des preuves avec des calculs, on s'est rendu compte qu'on était obligé de prendre les "résultats" de calcul presque comme axiomes. C'est quand-même dommage.

Je crains un peu que le calcul soit souvent un prétexte pour garder une liberté de notations et ne pas trop se justifier. Quand on regarde les notations du calcul différentiel et intégrale, les traditions pour écrire les extensions de corps, etc, force est de constater que la plupart du temps, rien que l'énoncé demande plus de temps pour être "compris" (dans le sens déchiffré) que pour être traité et presque chaque domaine "invente" un peu trop facilement "sa" manière d'écrire (notations d'Einstein, etc).

Dernière critique: au fond la science c'est "trouver, découvrir des certitudes". N'est-ce pas un peu bizarre qu'elle détruise d'un côté (petits signes les uns sur les autres, liberté notationnelle, etc) ce qu'elle cherche de l'autre?

Psychanalytiquement, (mais c'est bcp plus subjectif), j'aurais tendance à penser que c'est une manière aussi de "se protéger" de la part de la communauté d'une ingérance extérieure et d'une "concurrence" éventuelle. "les calculs montrent que.."; "bon, c'est juste un calcul, je vous l'épargne.."; etc.

Compte-tenu de mon inculture, je ne peux pas faire l'hypothèse que mon échantillon est représentatif, mais presque à chaque fois, dans la mare d'énoncés que je vois, que je tombe sur un énoncé que je comprends, l'auteur s'est gourré, a fait une coquille ou parfois même une erreur due à son "mépris" de l'aspect "hors-calcul". Dernier exemple*** en date, lu dans le train, l'auteur, pourtant quelqu'un de très bien, écrit dans sa liste d'exercice proposés:

*** je tiens à dire que je prends celui-ci qui date d'hier, mais c'est avec un taux élevé que je constate ça

Soit $K$ un corps et $E$ un ensemble infini. On s'intéresse à l'anneau $A$ des applications de $E$ dans $K$. Prouver que les idéaux maximaux de $A$ sont exactement les ensembles de la forme $\{f/ f(a)=0\}$ pour un élément de $E$.

Je ne crois pas que ce soit juste une coquille, mais plus profondément une dérive "culturelle". Je crois qu'il y a une forte tendance à se dire que, mis à part l'aspect calculatoire, le reste n'est "pas important" et que "en gros l'idée c'est que" et que "l'intendance doit suivre". Dans l'exemple précédent, l'intendance, par exemple, c'est rien moins que l'infini: l'énoncé est faux (avec l'axiome du choix) et est équivalent à la négation de l'axiome de l'ultrafiltre, de haute lutte finalement découvert lui-même comme plus fort que rien et strictement moins fort que l'axiome du choix.

Pour connecter ce post avec ce que je disais avant dans un autre fil, je pense que tout ceci mérite reflexion, car les sites de profs, de matheux, d'enseignants ont une forte influence sur la jeunesse. Et si les "vieux" présentent les maths aux jeunes (même brillants, d'ailleurs les autres s'en foutent) sous ce jour calculatoire, il ne faudra pas s'étonner que le reste, à terme sera perdu. Il n'y a pas de magie: à mon avis un jeune aujourd'hui qui "se chauffe" à devenir champion de "rubics cube" ou d'arithmétique ou d'analyse numérique, etc, etc, il n'y a pas de raison qu'il revienne facilement plus tard sur ces "non"choix pour commencer à réfléchir.

Attention: ceci ne sous-entend pas que "calculer est facile", on sait même prouver très facilement que les réponses aux questions calculatoires forment un ensemble non récursif, mon propos est plutôt de dire "quand est-ce qu'on "freine" un peu et qu'on reflechit?".

Donc questions:

1) En profondeur, en essence qu'est-ce qu'un calcul?

2) Qu'apportent-t-il? EXEMPLES de calculs qui ont vraiment été fructueux, en tant que tels! (Botter en touche sur une question pareille ce serait vraiment un aveu).

3) Quelle compétence calculatoire doit-on raisonnablement attendre de l'enseignant? (Force est de constater, apparemment, que puisque les auteurs de sujets de concours "pensent" qu'ils ne peuvent plus rien attendre de réfléchi des candidats, ils se "rabattent" sur de l'exigence calculatoire. Mais, honnêtement et concrêtement qu'est-ce que ça apporte vraiment à l'enseignant?)

4) Dans la cadre de la question (3); ie de l'enseignement, quelle réconciliation peut-on tenter entre "calcul" et certitude (il y a plein de gens qui ne sont pas au courant que par définition "maths = recherche de certitudes absolues" et qui pensent que les matheux calculent (dans le sens "ils ne pensent pas, ils calculent"). C'est un peu bête et surtout dommageable, non? Et ce n'est pas "moi" qui pense ça, ça va sans dire, mais j'avoue que quand je défends les matheux, je suis de plus en plus perplexe si je m'interroge sur la sincérité de mes dénégations à ces "accusations")