[Entier et infini] problème du sac (relativement long)

[Anonyme]

Bonjour à tous,
voilà j'ai récemment découvert un problème très instructifs (que j'ai choisi
d'appeler "problème du sac").
J'ai essayé d'approfondir un peu tout ça, et je vous livre ici quelques
reflexions que me laissent perplexe... Qu'en pensez-vous ?

Tout d'abord, le problème :

Soit un grand sac initialement vide et un ensemble de boules numérotées
(donc indéxées par N).
On établit le porecédé itératif suivant :

*****
Etape 1 :
On met dans le sac les boules numérotées de 1 à 10
On enlève la boule 1 du sac

Etape 2 :
On met dans le sac les boules numérotées de 11 à 20
On enlève la boule 2 du sac

(...)

Etape n :
On met dans le sac les boules numérotées de 10*(n-1)+1 à 10*n
On enlève la boule n du sac
******

On effectue ce procédé une infinité de fois.
Question : combien restera-t-il de boules à la fin ?

On aurait tendance à repondre une infinité puisqu'à chaque étape on rajoute
10 boules et on en enlève une.
Cependant, une simple démonstration permet de nous prouver le contraire.

En effet si le sac est non-vide, il reprèsente une partie non-vide de N DONC
il admet un plus petit élèment n0.
Or n0 est enlevé du sac à l'étape n0 !
Donc le sac est vide...

Voici deux variantes auxquelles j'ai pensé, mais je ne sais pas comment
interpreter les résulats, qu'en pensez vous ?

VARIANTE 1 :

Au lieu d'ôter la boule n à l'étape n, on effectue plutot le processus
suivant.

Soit En l'ensemble des boules présentes dans le sac à l'étape n.
A l'étape (n+1) on rajoute les 10 prochaines boulets et on ôte max(p dans
En).

Ainsi on aurait :

{1,2,3,4,5,6,7,8,9,10}
{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,20} (car 10 est le max de E1)
{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,30}
(car 20 est le max de E2)
etc. etc.

Cette fois-ci la démonstration précedente est caduque et on serait porté à
penser que le cardinal de l'ensemble En tendrait effectivement vers l'infini
avec n.

Pourtant à chaque étape on enlève effectivement une boule et on en rajoute
une comme lors de l'expérience précedente.
Le fait de dire qu'à chaque étape le cardinal de En augmente puis de passer
à la limite n'est pas satisfaisant car ça s'applique également au problème
précedent !
Comment conclure ?
Je soupçonne une histoire de bijection, surjection, injection entre des
ensembles de cardinal infini mais je n'arrive pas à formaliser tout ça,
qu'en pensez vous ?


VARIANTE 2 :

Cette fois-ci les boules ne sont plus numérotées et sont indiscernables au
toucher.
A chaque étape, on rajoute 10 boules dans le sac et on en enlève une au
hasard.
Un observateur qui assisterait à l'expérience mais qui n'apercevrait pas les
numéros des boules pensera qu'il s'agit de la même expérience qu'au début.
Formellement pourquoi est-ce différent ?

Merci d'avance pour vos réponses, contributions et lumières sur ce problème

Pierre

[Anonyme]

> On effectue ce procédé une infinité de fois.

Pas possible ça ... tu définis ça comment ?

[Anonyme]

On Fri, 3 Sep 2004 15:03:50 +0200, Bernard wrote:
>Voici deux variantes auxquelles j'ai pensé, mais je ne sais pas comment
>interpreter les résulats, qu'en pensez vous ?
>
>VARIANTE 1 :
>
>Au lieu d'ôter la boule n à l'étape n, on effectue plutot le processus
>suivant.
>
>Soit En l'ensemble des boules présentes dans le sac à l'étape n.
>A l'étape (n+1) on rajoute les 10 prochaines boulets et on ôte max(p dans
>En).
>
>Ainsi on aurait :
>
>{1,2,3,4,5,6,7,8,9,10}
>{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,20} (car 10 est le max de E1)
>{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,30}
>(car 20 est le max de E2)
>etc. etc.
>
>Cette fois-ci la démonstration précedente est caduque et on serait porté à
>penser que le cardinal de l'ensemble En tendrait effectivement vers l'infini
>avec n.
>
>Pourtant à chaque étape on enlève effectivement une boule et on en rajoute
>une comme lors de l'expérience précedente.

On en ajoute 10, pas une...

>Le fait de dire qu'à chaque étape le cardinal de En augmente puis de passer
>à la limite n'est pas satisfaisant car ça s'applique également au problème
>précedent !
>Comment conclure ?
>Je soupçonne une histoire de bijection, surjection, injection entre des
>ensembles de cardinal infini mais je n'arrive pas à formaliser tout ça,
>qu'en pensez vous ?

Oh, c'est plus simple : tu as enlevé toutes les boules de rang un
multiple de 10, il reste toutes les autres (celles dont le rang n'est
pas un multiple de 10), qui sont en nombre infini.


>VARIANTE 2 :
>
>Cette fois-ci les boules ne sont plus numérotées et sont indiscernables au
>toucher.
>A chaque étape, on rajoute 10 boules dans le sac et on en enlève une au
>hasard.
>Un observateur qui assisterait à l'expérience mais qui n'apercevrait pas les
>numéros des boules pensera qu'il s'agit de la même expérience qu'au début.
>Formellement pourquoi est-ce différent ?

Je suppse que tu tires les boules de façon équiprobable. La question
est de savoir, en considérant une boule quelconque, quelle est la
probabilité qu'elle soit ôtée à un moment donné. Prenons la boule 1,
par exemple.

Elle a une chance sur 10 d'être retirée au premier tour. Puis, si elle
est toujours là (9 chances sur 10), elle a 1 chance sur 19 de partir au
second, puis (18/19 chances) une chances sur 28, etc.

Soit u_n la probabilité qu'elle soit retirée au rang n.
u_n = v_n * 1 / (9n + 1)
avec v_1 = 1, v_{n+1} = v_n * (1 - 1 /(9n + 1))

La probabilité qu'elle soit retirée un jour est la somme des u_n,
pour n entre 1 et l'infini. Soit cette limite est inférieure à 1,
et dans ce cas à la limite le sac est « infini », car les boules
suivantes ont une probabilité supérieure de rester, soit cett elimite
est 1, et la boule 1 n'est pas dans le résultat, pour presque toutes les
parties que l'on jouera. Comme je pense que les boules suivantes auront
une probabilité de rester qui ressemble, dans ce cas, chaque boule aura
une probabilité 1 d'avoir été retirée à un moment donné, et à la limite
le sac est vide.

J'ai un peu la flemme de faire le calcul exact, mais je soupçonne
fortement que la limite de la série en question est 1, et qu'en
conséquence, le sac est « statistiquement » vide, c'est-à-dire que si
tu te donnes un entier quelconque, alors la probabilité que la boule en
question soit présente au bout du compte est nulle.

Bien cordialement,

--
Frédéric BÉAL

[Anonyme]

> Etape 1 :
> On met dans le sac les boules numérotées de 1 à 10
> On enlève la boule 1 du sac
> Etape n :
> On met dans le sac les boules numérotées de 10*(n-1)+1 à 10*n
> On enlève la boule n du sac
> ******
>
> On effectue ce procédé une infinité de fois.
> Question : combien restera-t-il de boules à la fin ?

> On aurait tendance à repondre une infinité puisqu'à chaque étape on rajoute
> 10 boules et on en enlève une.

Euh, un raisonnement formel donne 10*infini-infini=infini-infini, et ceci
s'appelle parfois une "forme indéterminée". Autrement dit, le raisonnement
formel ne donne pas de réponse.

> Cependant, une simple démonstration permet de nous prouver le contraire.
> En effet si le sac est non-vide, il reprèsente une partie non-vide de N DONC
> il admet un plus petit élèment n0.
> Or n0 est enlevé du sac à l'étape n0 !
> Donc le sac est vide...

Exactement.

> Je soupçonne une histoire de bijection, surjection, injection entre des
> ensembles de cardinal infini mais je n'arrive pas à formaliser tout ça,
> qu'en pensez vous ?

Si ça t'intéresse, cherche peut-être du côté de la notion de "limite
inductive".

--
Yves

[Anonyme]

On Fri, 3 Sep 2004 15:19:56 +0200, Julien Santini wrote:[color=green]
>> On effectue ce procédé une infinité de fois.
>
>Pas possible ça ... tu définis ça comment ?[/color]

? Tu n'ajoutes que des boules à des positions dont le min tend vers
l'infini. En dessous, tu fais une intersection ; au dessus, on s'en
fiche, vu qu'à un indice suffisamment grand on l'aura dépassé.

Il s'agit donc d'une gentille intersection d'ensembles, en bidouillant
un peu. Soit E(n) l'ensemble des boules présentes au rang n, on a donc
E(n) inclus dans [1; 10n]. On définit F(n) = E(n) union [10n+1, -> [
et la limite est l'intersection des F(n).

Cela te convient-il ?

--
Frédéric

[Anonyme]

"Bernard" , dans le message (fr.education.entraide.maths:57465), a écrit
> Etape 1 :
> On met dans le sac les boules numérotées de 1 à 10
> On enlève la boule 1 du sac
> Etape n :
> On met dans le sac les boules numérotées de 10*(n-1)+1 à 10*n
> On enlève la boule n du sac
> On effectue ce procédé une infinité de fois.
> Question : combien restera-t-il de boules à la fin ?


Euh, un raisonnement formel donne 10*infini-infini=infini-infini, et ceci
s'appelle parfois une "forme indéterminée". Autrement dit, le raisonnement
formel ne donne pas de réponse.

> Cependant, une simple démonstration permet de nous prouver le contraire.
> En effet si le sac est non-vide, il reprèsente une partie non-vide de N
> DONC il admet un plus petit élèment n0.
> Or n0 est enlevé du sac à l'étape n0 !
> Donc le sac est vide...

Exactement.

--
Yves

[Anonyme]

> un peu. Soit E(n) l'ensemble des boules présentes au rang n, on a donc
> E(n) inclus dans [1; 10n]. On définit F(n) = E(n) union [10n+1, -> [
> et la limite est l'intersection des F(n).
>
> Cela te convient-il ?
>

Non ça j'ai compris. A l'étape n on a les boules [1;10n] - [1,n]. La liminf
de cette ensemble est l'ensemble vide, la limsup de cette ensemble aussi,
donc la limite est l'ensemble vide. Ce qui m'inquiétait c'est que
conceptuellement l'auteur du post présente le phénomène comme étant
"étonnant", et c'est là que je dis, en réalité, tu considères toujours un
état correspondant à un nombre fini de manips.

[Anonyme]

"Julien Santini" , dans le message (fr.education.entraide.maths:57472),
a écrit :

> Non ça j'ai compris. A l'étape n on a les boules [1;10n] - [1,n]. La liminf
> de cette ensemble est l'ensemble vide, la limsup de cette ensemble aussi,
> donc la limite est l'ensemble vide.

Ah, ben tu réponds à la question de "formaliser la question":
effectivement la notion de limite d'ensemble est la bonne, et elle
n'existe pas toujours: prnedre le processus où à la (2n-1)ième étape on
pose une pièce sur une table et à la (2n)ième on la ra reprend: la
question "combien y a-t-il de pièces sur la table au bout d'un temps
infini?" n'a pas de sens.

(pour la définition d'une limite sup/inf de parties, voir
http://encyclopedia.thefreedictionary.com/limit%20superior par exemple)

--
Yves

[Anonyme]

le paradoxe porte son nom


1 mn avant minuit, les boules numérotées de 1 à 10 sont placées dans une
urne et la boule 1 retirée.
1/2 mn avant minuit, les boules 11 à 20 y sont placées et la boule 2 retirée
1/3 mn avant minuit, les boules 21 à 30 sont placées et la 3 retirée
combien de boules restera-t-il à minuit?

(le tout étant d'arriver à concevoir une action comportant une infinité
d'étapes, ce qui est humainement impossible, mais tout à fait plausible dans
la mesure où chacun sait qu'après minuit, c'est demain!)