Défi 23

par **Zebulon** » 18 Jan 2007, 23:32

sandrine_guillerme a écrit:yos ,

2^(n-1) ?

Je trouve 30 pour n=6. A moins que j'en aie oubliées ?

par **Joker62** » 18 Jan 2007, 23:35

Moi j'en suis arrivé là,
maintenant reste à voir combien de fois on coupe 2 droites, combien de fois on en coupe 1
Pour ce qui est de combien de fois on en coupe pas c'est simple, c'est 2 fois, avec les deux autres points délimitant la région dans laquelle on se trouve

Effectuons une réccurence :
La propriété à vérifiée étant P(n) : le nombre de régions intérieurs au cercle étant de 2^(n-1)

On vérifie pour n = 2, On a dans ce cas de figure un cercle et une corde, on a donc 2 régions
De plus 2^(2-1) = 2 donc c'est ok pour là !

Supposons ensuite avoir construit une famille de point :

tous distincts définissant 2^(n-1) régions.

On est sur que parmis ces 2^(n-1) régions, il existe exactement n régions possédant une partie du cercle comme côté.

On construit le point

. Ce point appartient donc à une de ces régions.
Les droites reliants les points devant être non concourrantes 3 à 3, on est sur qu'en reliant le nouveau point avec un des anciens, on coupera au plus 2 droite.
En coupant 0 droite, on rajoute 1 région
En coupant une seule droite, on rajoute 2 régions
En coupant 2 droite, on rajoute 3 régions

Reste à prouver que le nombre de régions créees vaut 2^(n-1)

par **sandrine_guillerme** » 18 Jan 2007, 23:38

Zebulon a écrit:Je trouve 30 pour n=6. A moins que j'en aie oubliées ?

Salut Zeb ! ça va toi?
Oui je crois que tu en as oublié mais peut être que je fais n'importe quoi .. je ne le fais que très vite parceque je suis complètement nase

par **Zebulon** » 18 Jan 2007, 23:43

sandrine_guillerme a écrit:Salut Zeb ! ça va toi?

Très bien, merci. Si on était sur un chat je te demanderais aussi, mais bon, ça risque d'encombrer... :we:

Sandrine a écrit:Oui je crois que tu en as oublié mais peut être que je fais n'importe quoi .. je ne le fais que très vite parceque je suis complètement nase

En recomptant deux fois de suite je trouve 31 ! :marteau:

par **sandrine_guillerme** » 18 Jan 2007, 23:44

Zeb, Je pense qu'on peut le démontrer !
en introduisant un nouveau point, on trace n nouveaux segments
en comptant combien on crée de nouvelles régions, deux fois plus de régions en passant de n à n+1 points, l'hypothèse que les droites ne sont pas concourantes joue beaucoup !
sinon, il n'y aurait pas de formule explicite,
mais seulement des bornes inf et sup
enfin bon, précisément, vu que je n'ai fait que des dessins sur ma feuille de brouillon, je ne saurais en dire plus
je laisse la main à tout les autres !!

par **Joker62** » 18 Jan 2007, 23:51

Moi pour n=6 je trouve bien 32 régions

par **sandrine_guillerme** » 18 Jan 2007, 23:52

Oué Moi aussi j'ai refais en fait .. finalement je m'intérésse a ce problème sympatique .. :ptdr:

par **Joker62** » 18 Jan 2007, 23:53

Bé ui ta toute ta vie pour tes exams ;)

par **Zebulon** » 18 Jan 2007, 23:54

sandrine_guillerme a écrit:Zeb, Je pense qu'on peut le démontrer !

Oui, mais ça m'énerve de ne pas bien les compter.

en introduisant un nouveau point, on trace n nouveaux segments
en comptant combien on crée de nouvelles régions, deux fois plus de régions en passant de n à n+1 points, l'hypothèse que les droites ne sont pas concourantes joue beaucoup !

OK mais comme ça ne me parassait pas évident et que je ne conjecturais rien... j'ai préféré passer par les croisements.

sinon, il n'y aurait pas de formule explicite,

Comment ça ? Il n'y aurait pas de formule explicite si c'était plus compliqué ??

Ceci dit, je ne dis pas que ta conjecture est fausse. J'en veux juste la preuve ! :we:

par **Zebulon** » 18 Jan 2007, 23:58

Joker62 a écrit:Reste à prouver que le nombre de régions créees vaut 2^(n-1)

Au final, il suffit de montrer lorsqu'on rajoute un point, chaque région déjà construite est coupée par exactement un nouveau segment.

par **sandrine_guillerme** » 18 Jan 2007, 23:59

Zebulon a écrit:Comment ça ? Il n'y aurait pas de formule explicite si c'était plus compliqué ??

Bah je pense que ça changera au fur et à mesures .

Zebulon a écrit:Ceci dit, je ne dis pas que ta conjecture est fausse. J'en veux juste la preuve ! :we:

Je verrai ce que je pourrais faire mais bon mes connaissances sont très limités

Mdr joker tu as raison !!

par **Joker62** » 19 Jan 2007, 00:05

Bé pour n = 3
On voit que si on rajoute un point, il ne coupe que 2 régions, il ne touche pas aux 2 autres.

J'en viens à m'intéresser à compter finalement tous les segments et à enlever ceux en trop, ça me fait un peu penser à la formule du crible j'pars de ce côté...

par **sandrine_guillerme** » 19 Jan 2007, 00:24

Allons y :

je me disais qu'en supposant qu'il y a 2^n régions pour n points
si on rajoute un n+1-ème point, on va tracer n segments
ces n segments vont créer 2^n régions nouvelles ; enfin c'est ce qu'on voudrait prouver
or mis à part deux cas particuliers un segment va croiser n-2 segments
les deux cas particuliers sont les segments qui relient le nouveau point au voisin directdonc créant 2 régions nouvelles exactement.

et voilà où j'en suis lol, entre deux manipulations et crises de nerfs lol

Yos tu ne peux toujours pas répondre ?

par **Zebulon** » 19 Jan 2007, 00:35

Voici où j'en suis (en cherchant une formule sur le nombre de croisements) :

Pour avoir p(n), on fait la somme de tous ces nombres (jusqu'à la n-ième ligne). En comptant par colonnes, on trouve :
la somme des n-3 premiers entiers plus
la somme des n-4 premiers multiples de 2 plus
la somme des n-5 premiers multiples de 3 plus
... plus..
C'est donc la somme des sommes des n-2-(k+1) premiers multiples de k, pour k=1 à n-3 :

C'est vrai, ça ?

(modification en rouge)

par **Imod** » 19 Jan 2007, 00:40

Bonjour à tous .

J'ai jeté un coup d'oeil au problème un peu tard mais de toute façon , je crois que je vais laisser la jeunesse se débrouiller :we: . Deux choses apparaissent très vite pour n points .
1°) Il y a n portions de disque .
2°) En évacuant les portions de disque et en considérant le polygône à n côtés restant . On peut remarquer que chaque diagonale issue d'un sommet A coupe chaque diagonale qui n'est pas issue de A . Il reste à compter le nombre de parts supprimées en éliminant une à une les diagonales issues de A puis le sommet A pour amorcer une récurrence .

Bon courage !

Imod

par **Joker62** » 19 Jan 2007, 01:00

Bon apparemment la conjecture c'est pas ça
Parce que si on part d'un pentagone, et que l'on rajoute un point, on ne peut que relier le nouveau point à 2 points.
Ce qui laisse les 32 régions ( 2^5 ) loin du compte

Donc si la conjecture merdouille, j'peux abandonner la récurrence et aller me coucher :)

par **Imod** » 19 Jan 2007, 01:15

La conjecture de Sandrine n'est pas démentie ni certifiée , en tout cas elle est vraie pour les premières valeurs de n . Si tu ne veux pas des pistes que te donnes , oublie les ! Je n'ai pas trop envie de me pencher sur ce défi non par manque d'intérêt mais parce que je veux laisser une place à d'autres intervenants .

Imod

par **Joker62** » 19 Jan 2007, 08:17

Non oui évidemment que si j'veux pas des conjectures des autres je cherche moi même. Mais c'est juste que j'avais remarquer que sa conjecture était exacte pour des petites valeurs de n, donc je m'étais pencher dessus, logique...

par **Zebulon** » 19 Jan 2007, 13:05

Un résultat intéressant :
je trouve

.
Reste à trouver la relation entre points d'intersection et régions.

par **Zebulon** » 19 Jan 2007, 13:53

Pour le lien entre f(n) (nombre de régions) et p(n) (nombre de points d'intersection), je trouve :
f(n)=f(n-1)+L(n)+n-1, avec L(n) étant la somme des termes de la n-ième ligne du tableau que j'ai fait au-dessus,
soit

En calculant, je trouve

d'où

.
Avec cette formule de récurrence, on a :

Et il y a ce 31 qui apparaît... 31 que je trouve et qui contredit la conjecture...
Hum hum...

Peut-être qu'en fait je me plante complètement... :mur:

Défi 23

Qui est en ligne