Compter des entiers

Alban_ · April 2018

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)...

Rescassol · April 2018

Bonjour,

Le nombre de couples $(a,b)$ tels que $-n \leq -2a+b \leq n$ est $2n^2+3n+1$.

Cordialement,

Rescassol

Alban_ · April 2018

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 ?

Poirot · April 2018

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.

jacquot · April 2018

Pour $n=5$, on a $61$ couples qui conviennent sur $121$ candidats.
Mon dénombrement ne vérifie pas la formule de Rescassol. 75098

Rescassol · April 2018

Bonjour,

Oui, tu as raison, Jacquot, c'est $2n^2+2n+1$.

Cordialement,

Rescassol

Rescassol · April 2018

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

Rescassol · April 2018

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

GaBuZoMeu · April 2018

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$.

Alban_ · April 2018

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 ?

Alban_ · April 2018

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 ?

GaBuZoMeu · April 2018

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}$$

Rescassol · April 2018

Bonjour,

La somme des termes d'une suite arithmétique, tu devrais connaître.
En quelle classe es tu ?

Cordialement,

Rescassol

Alban_ · April 2018

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

Compter des entiers

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 8