Compter des entiers
Bonjour et désolé pour le titre pas du tout explicite. Je cherche à compter le nombre d'entiers $a$ et $b$ appartenant à $\{-n,...,n\}$ tels que $-n\leq -2a+b\leq n$ ($n$ étant un entier naturel non nul fixé).
Je ne vois pas tellement comment m'y prendre : je fixe $a$ dans $\{-n,...,n\}$ et je compte le nombre de $b$ dans $\{-n,...,n\}$ tels que $-n+2a \leq b\leq n+2a$. Mais je suis un peu bloqué là (c'est-à-dire pas très loin)...
Je ne vois pas tellement comment m'y prendre : je fixe $a$ dans $\{-n,...,n\}$ et je compte le nombre de $b$ dans $\{-n,...,n\}$ tels que $-n+2a \leq b\leq n+2a$. Mais je suis un peu bloqué là (c'est-à-dire pas très loin)...
Réponses
-
Bonjour,
Le nombre de couples $(a,b)$ tels que $-n \leq -2a+b \leq n$ est $2n^2+3n+1$.
Cordialement,
Rescassol -
Maintenant que je sais que la réponse est 42, je suis bien avancé... merci Rescassol
Bon, si je fixe $i$ dans $\{-n,..,n\}$ et que je m'intéresse au nombre $s(i)$ d'entiers $a,b$ dans $\{-n,..,n\}$ tels que $-2a+b=i$, alors le nombre que je cherche sera la somme des $s(i)$ pour $i$ entre $-n$ et $n$. Je cherche donc le nombre d'entiers $a,b$ dans $\{-n,..,n\}$ tels que $-2a+b=i$. Si je fixe $a$ dans $\{-n,..,n\}$, alors $b = i+2a$ doit être compris entre $-n$ et $n$, ce qui implique $a$ compris entre $(-n-i)/2$ et $(n-i)/2$ soit $n+1$ possibilités. J'obtiens donc en sommant $(n+1)(2n+1)$ couples, soit la réponse de Rescassol.
Je n'aime pas trop la façon dont j'écris cela, notamment "si je fixe $a$, ..., alors $a$ est compris entre". Comment rendre mon bricolage rigoureux ? -
L'histoire du "je fixe $a$" revient à partitionner ton ensemble de couples. Formellement, $$ \{(a,b) \in \{-n, \dots, n\}^2 \mid -n \leq -2a+b \leq n\} = \bigcup_{a \in \{-n, \dots, n\}} \{(a,b) \in \mathbb Z^2 \mid b \in \{-n, \dots, n\} \text{ et } -n \leq -2a+b \leq n\},$$ où la réunion est disjointe. Il ne reste plus qu'à compter individuellement chaque cardinal.
-
Pour $n=5$, on a $61$ couples qui conviennent sur $121$ candidats.
Mon dénombrement ne vérifie pas la formule de Rescassol. -
Bonjour,
Oui, tu as raison, Jacquot, c'est $2n^2+2n+1$.
Cordialement,
Rescassol -
Bonjour,
def compte(n): cpt=0 for a in range(-n,n+1): for b in range(-n,n+1): if -n<=-2*a+b<=n: cpt+=1 return cpt print(compte(5)) # Ceci répond 61
Cordialement,
Rescassol -
Bonjour,
Une variante donnant une jolie figure:import matplotlib.pyplot as plt def compte(n): cpt=0 for a in range(-n,n+1): for b in range(-n,n+1): if -n<=-2*a+b<=n: cpt+=1 T.append((a,b)) return cpt T=[] print(compte(50)) # Ceci répond 5101 plt.plot(T,'.r') plt.show()
Ce qui donne:
Cordialement,
Rescassol -
Le petit tableau de jacquot montre bien comment compter sans peine (on compte les $b$ pour $a$ allant de $-n$ à $0$ puis de $1$ à $n$ :
$$\begin{array}{cccccc}
1&3&5&\ldots&2n-1&2n+1\\
2n-1&2n-3&2n-5&\ldots&1&
\end{array}$$
ce qui fait au total $2n\times n + 2n+1$. -
Effectivement, je reprends mon message précédent pour voir ce qui cloche. J'en reste à la version "intuitive" sans passer par les partitions de Poirot qui me permettent effectivement d'écrire ça proprement.
Je fixe donc $i$ dans $\{-n,..,n\}$ et que je m'intéresse au nombre $s(i)$ d'entiers $a,b$ dans $\{-n,..,n\}$ tels que $-2a+b=i$. Si je fixe $a$ dans $\{-n,..,n\}$, alors $b = i+2a$ doit être compris entre $-n$ et $n$, ce qui implique $a$ est un entier compris entre $(-n-i)/2$ et $(n-i)/2$. J'avais affirmé tout à l'heure que cela donnait $(n-i)/2-(-n-i)/2+1=n+1$ possibilités, ce qui n'est le cas que si $n$ et $i$ ont la même parité :-X (sinon, il y en a seulement $n$).
En distinguant des cas suivant la parité de $n$, je pourrais sommer mes $s(i)$ correctement et arriver sans doute au bon résultat. Mais est-ce qu'il n'y a pas plus simple que ces distinctions de cas pénibles ? -
Mon dernier message ayant dû partir juste après celui de GaBuZoMeu, je viens seulement de le voir. Je ne suis pas sûr de comprendre : tu fixes successivement $a$ à $-n$ jusqu'à $0$, ce qui donne en lisant le tableau $1$, $3$, $5$, ..., $2n+1$ possibilités pour $b$. Puis idem pour $a$ variant de $1$ à $n$, ce qui donne $2n - 1$, $2n - 3$, ..., $1$ possibilités pour $b$.
Donc au total $\sum_{k=0}^{n}(2k+1)+\sum_{k=0}^{n-1}(2k+1)=2n^2+2n+1$ possibilités. Je n'ai pas compris le calcul du total que tu as fait ? -
On fixe $a$ entre $-n$ et $n$ et on compte les $b$ tels que
$$\max(-n-2a,-n)\leq b\leq \min(n-2a,n)\;.$$
Si $-n\leq a\leq 0$, alors $\max(-n-2a,-n)=-n-2a$ et $\min(n-2a,n)=n$. Le nombre de $b$ est $2n+1+2a$.
Si $0< a\leq n$, alors $\max(-n-2a,-n)=-n$ et $\min(n-2a,n)=n-2a$. Le nombre de $b$ est $2n+1-2a$.
Pour faire le calcul du total, je me sers de la disposition en tableau des résultats : j'ai $n$ colonnes telles que la somme dans chaque colonne est $2n$, d'où le $n\times 2n$ plus une colonne avec $2n+1$ tout seul.
Tu n'as jamais vu une disposition de ce type pour montrer que la somme des entiers de $1$ à $n$ est la moitié de $n\times (n+1)$ ?
$$\begin{array}{ccccc}
1&2&\ldots&n-1&n\\
n&n-1&\ldots&2&1
\end{array}$$ -
Bonjour,
La somme des termes d'une suite arithmétique, tu devrais connaître.
En quelle classe es tu ?
Cordialement,
Rescassol -
OK, merci de la précision. Je ne comprenais pas pourquoi tu avais disposé les nombres ainsi, je pensais que c'était pour expliquer ce que tu voyais dans le tableau de jacquot et pas pour calculer la somme. Pas de problème pour le Gauss' Trick
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres