Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 02-11-2010 08:43:21

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

Coordonnées dans le triangel des entiers

Un petit concours organisé par Wild About Math (ça faisait longtemps)

Soit le triangle infini composé des entiers suivant :

1
2  3
4  5  6
7  8  9 10
11 12 13 14 15
16 17 18 19 20 21
   . . .

Chaque ligne R possède R nombre et chaque colonne C a un nombre infini de nombres. Les lignes et les colonnes commencent à 1. On définit une fonction FF(R,C) qui a chaque ligne R et chaque colonne C donne la valeur dans ke triangle associée.
Exemple : F(1,1) = 1, F(2,1) = 2, et F(2,2) = 3.
Notez que F(R,C) n'est défini que lorsque 1 <= C <= R.

Exercice 1 : Trouvez la formule de F(R,C) dans l'intervalle de définition. Développez votre raisonnement.

Exercice 2 : Déterminer une formule, qui pour un entier donné N, permet de retrouver R et C.

Les modalités d'envoi de votre réponse sont disponibles sur le site (en anglais). Il y a une calculatrice a gagner. Les réponses proposées ici sont cachées jusqu'à la fin du concours.

http://wildaboutmath.com/2010/11/01/ti- … e-contest/



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 02-11-2010 10:10:42

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Coordonnées dans le triangle des enttiers

F(R,1) = 1+ somme de 1 à (R-1)= 1+1+2+3+....+(R-1)

F(R,C) = F(R,1) + (C-1)

donc N = 1+2+3....+R+C=  (R-1)X(R/2) +C



Pour l'inverse, il faut considérer le nombre N' = F ( R,1 )

N'=R(R-1)+1

D'ou R= racine( 2N' - 7/4 )  + 1/2

Cette valeur ne prenant des valeurs entières que pour C=1, on en déduit que

R= ENT( Racine ( 2N-7/4 ) + 1/2 )

et donc que  (à partir de R précédemment trouvé) :

C= N -  R(R-1)/2

 #3 - 02-11-2010 10:53:21

engine
Professionnel de Prise2Tete
Enigmes résolues : 37
Messages : 351

coordonnées dans le troangle des entiers

J'ai pas bien compris : il est où l'intervalle de définition ?


plouf

 #4 - 02-11-2010 11:35:30

gabrielduflot
Expert de Prise2Tete
Enigmes résolues : 34
Messages : 609

coordonnées dans le ttiangle des entiers

[TeX]F(R;C)={{(R-1)\times R}\over 2} + C[/latex] car on on a la somme des entiers de 1 à R-1 avant d'ajouter C

Soit N un entier naturel alors il existe [latex]R\in N tel que {{R^2 - R}\over 2}<= N < {{R^2+R}\over 2}[/latex] donc on va résoudre l'équation R²+R-2N et on va prendre R la partie entière de la solution positive donc[latex] R=E({{-1+\sqrt{1+8N}}\over 2})[/latex] et[latex] C=N - {{R^2 - R}\over 2}[/TeX]

 #5 - 02-11-2010 11:44:11

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Coordonnées dans le triangle des entier

On commence par remarquer que
> F(k,i) = F(k,j) + (i-j)
(sur une même ligne, la différence entre deux nombres est égal au nombre de cases pour aller de l'un à l'autre)

> F(k+1, 1) = 1 + F(k, k)
(en début de ligne, on a le nombre immédiatement après le dernier de la ligne précédente).

On attaque.
1. On va d'abord montrer que le dernier nombre d'une ligne n est n(n+1)/2, par récurrence.
=> pour n=1, le dernier chiffre est bien 1
=> Hypothèse de récurrence: pour une ligne n, le dernier nombre vaut F(n,n) = n(n+1)/2
=> Posons N = n+1, le premier nombre de la ligne N vaut F(N,1) = n(n+1)/2 +1, et le dernier vaut F(N,N) = F(N,1) + N - 1 = N + n(n+1)/2 = (n+1) + n(n+1)/2 = (n+1)(n+2)/2 = N(N+1)/2, CQFD

Du coup, pour 1<=j<=k, F(k,j) = F(k,k) + (j-k) = k(k+1)/2 +j - k = k(k-1)/2 + j

2. Un nombre N est sur une ligne k si et seulement si il est compris entre le dernier nombre de la ligne k-1 (exclu) et le dernier nombre de la ligne k. Autrement dit, F(k-1,k-1) < N <= F(k, k); ou encore
> k(k-1)/2 < N <= k(k+1)/2
> k(k-1) < 2N <= k(k+1)
k(k-1) < 2N si et seulement si k²-k-2N < 0.
Le delta de ce polynôme vaut 1+8N, positif strictement, donc on a 2 racines. Ce polynôme est donc négatif entre ses racines, qui sont [latex]\frac{1-\sqrt{1+8N}}{2}[/latex] et [latex]\frac{1+\sqrt{1+8N}}{2}[/latex]
De la même manière k(k+1 >= 2N si et seulement si k est inférieur à
[TeX]\frac{-1-\sqrt{1+8N}}{2}[/latex] (qui est négatif, donc on oublie) ou bien s'il est supérieur à [latex]\frac{-1+\sqrt{1+8N}}{2}[/TeX]
Donc [latex]\frac{-1+\sqrt{1+8N}}{2} <= k < \frac{1+\sqrt{1+8N}}{2}[/latex]
La différence entre les deux bornes de k vaut 1, autrement dit il n'existe qu'un entier k entre ces deux bornes.Au final donc [latex]k = \lceil \frac{-1+\sqrt{1+8N}}{2} \rceil[/latex]

Ayant identifié la ligne k sur laquelle se trouve notre nombre N, il ne reste plus qu'à dérouler un peu les calculs:
N = F(k,j) = F(k,k) + j-k = k(k+1)/2 + j-k = k(k-1)/2 + j
j = N - k(k-1)/2

Au final, on a donc:
[TeX]=> F(k,j) = \frac{k(k-1)}{2} + j[/TeX]
[TeX]=> N = F(\lceil \frac{\sqrt{1+8N}-1}{2} \rceil, N - \frac{\lceil \frac{\sqrt{1+8N}-1}{2} \rceil . \lceil \frac{\sqrt{1+8N}-3}{2} \rceil}{2})[/TeX]

 #6 - 02-11-2010 14:13:40

McFlambi
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 144

Coordonnées das le triangle des entiers

1. F(R,C) est le nombre situe dans la ligne en dessous du triangle comptant (R-1)R/2 elements, et c'est le C-ieme element de cette ligne, donc

F(R,C)=R(R-1)/2+C

2. Soit N un nombre, j'appelle M le nombre qui est sur la meme ligne mais a la fin de celle ci, et m le denier nombre sur la ligne du dessus. Alors M et m sont de la forme:

m = R(R-1)/2
M = R(R+1)/2 = m+R

soit

R(R-1)/2 < N <= R(R+1)/2

que je transforme en

2m = R(R-1) < 2N <= R(R+1) = 2M = 2m+2R

Ensuite si je regarde la fonction croissante monotone pour x>0
[TeX]f(x)=x(x+1)=x^2+x[/TeX]
sa reciproque pour x est (valeurs >0)
[TeX]g(y) = \frac{ \sqrt{4 y+1}-1}2[/TeX]
Donc      [latex]R=\lceil\frac{ \sqrt{8 N+1}-1}2\rceil[/latex]

et finalement
[TeX]C=N-R(R-1)/2[/TeX]

 #7 - 02-11-2010 20:23:08

supercab
Habitué de Prise2Tete
Enigmes résolues : 43
Messages : 20

Coordonnées ans le triangle des entiers

Exercice 1:
Soient R et C des entiers.
On remarque d'abord que, pour C≠1, [latex]F(R,C) = F(R,C-1) +1[/latex].
Donc nous avons deja:
[TeX]F(R,C)=C-1+F(R,1)[/TeX]
Mais on a de nouveau une relation de récurrence:
[TeX]F(R,1)=F(R-1,1)+R-1[/TeX]
D'où[latex] F(R,1)=1+ \frac{ R *(R-1)}{2}[/latex]

Finalement:
[TeX]F(R,C) = C+ \frac{R *(R-1)}{2}[/TeX]
Exercice 2:
Soit N un entier.
Notons G l'application qui a R associe F(R,1)
[TeX]G(R)\leq N<G(R+1)[/TeX]
Or G admet une application réciproque : [latex]G^{-1}(X)=\frac{1+ \sqrt{8X-7}}{2}[/latex] qui est strictement croissante; donc:
[TeX]R\leq G^{-1}(N)<R+1[/TeX]
donc R est la partie entière de [latex]G^{-1}(N)[/latex].
[TeX]R=E(\frac{1+ \sqrt{8N-7}}{2})[/latex].

On a aisément que C=N-F(R,1)+1, donc finalement:

[latex]\{{R=E(\frac{1+ \sqrt{8N-7}}{2}) \atop C=N-\frac{R*(R-1)}{2}}[/TeX]

 #8 - 02-11-2010 22:10:02

Yannek
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 60

Coordonnées dans le triangl edes entiers

[TeX]F(R,C)=\frac{R(R-1)}2+C[/TeX]
Le premier terme donne le nombre de nombres utilisés dans la pyramide jusqu'à la rangée R-1 (somme des R-1 premiers entiers), le second le nombre de nombres utilisés dans la rangée numéro R.

Pour la réciproque, si N>0,
[TeX]F(R,C)=N\Leftrightarrow \left\{\begin{array}{l}R=\left[\frac{1+\sqrt{8N-7}}2\right]\\ C=N-\frac{R(R-1)}2\end{array}\right.[/TeX]
En effet, R est la plus grande solution entière de l'inéquation [latex]\frac{R(R-1)}2\leq N-1[/latex]. Les entiers solutions de cette inéquation sont dans l'intervalle [latex]\left[\frac{1-\sqrt{8N-7}}2,\frac{1+\sqrt{8N-7}}2\right]~[/latex].

Le plus grand est la partie entière de la borne supérieure de l'intevalle. On obtient C d'après la formule ci dessus.

 #9 - 02-11-2010 22:32:24

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Coordonnées dans le triangle ddes entiers

P.S. Un jour, il faudra m'expliquer comment vous écrivez des belles formules avec racine, sigma....

 #10 - 04-11-2010 00:16:48

luthin
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 124

Coordonnés dans le triangle des entiers

1) Je commence par calculer le premier élément d'une ligne quelconque. Il suffit d'ajouter 1 à la somme des nombres d'éléments des lignes supérieures.
[TeX]F(R,1)=1+(R-1)+(R-2)+...+1=1+\frac{(R-1)R}{2}[/TeX]
Puis, il n'est n'est pas difficile de voir que:
[TeX]F(R, C)=F(R,1)+C-1[/TeX]
Ce qui donne:
[TeX]\fbox{F(R,C)=\frac{(R-1)R}{2}+C}[/TeX]
2) Moins facile que ça en a l'air!
Soit un élément [latex]N[/latex] du triangle.
Alors il est plus petit que le premier de la ligne suivante et plus grand que le dernier de la ligne précédente, soit:
[TeX]F(R,1)-1<N<F(R+1,1)[/TeX]
Ce qui est équivalent à:
[TeX]\fbox{\frac 12\left(\sqrt{1+8(N-1)}-1\right)<R<\frac 12\left(\sqrt{1+8N}+1\right)}[/TeX]
[TeX]R[/latex] est donc l'unique entier vérifiant ces inéquations, puis on en déduit facilement [latex]C[/latex]:
[latex]\fbox{C=N-\frac{(R-1)R}{2}}[/TeX]

 #11 - 04-11-2010 06:59:45

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

coordonnées dans le triangle deq entiers

1/
[TeX]F(R,C)=\sum^{R-1}_{i=1}i+C=\frac{R(R-1)}{2}+C[/TeX]
2/
ce qui donne à partir de n
trouver le plus grand R tel que
[TeX]n-\frac{R(R-1)}{2}>0[/TeX]
le reste donne C


The proof of the pudding is in the eating.

 #12 - 05-11-2010 00:41:58

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

coprdonnées dans le triangle des entiers

Amusant. Je crois que j'ai croisé ça il y a quelques années dans le championnat FFJM mais je n'ai pas le courage de chercher quand.

Tout le raisonnement se base sur la formule de la somme des premiers entiers:
[TeX]\sum_{k=1}^n{k}=\dfrac{n(n+1)}2[/TeX]
La première ligne contient 1 nombre, la seconde 2, donc le dernier nombre de la 2ème ligne est 1+2=3. La troisième ligne contient 3 nombres et le dernier nombre de la 3ème ligne est donc 1+2+3=6.
On voit donc aisement que le dernier nombre de la ligne R est donc R(R+1)/2.
Pour un nombre sur la ligne R, le dernier nombre de la ligne R-1 est R(R-1)/2 et le nombre n est le "C-ième" de la ligne R.

On a donc [latex]F(L,C)=\dfrac{L(L-1)}2+C[/latex]
(J'utilise L(igne) au lieu de R(ow) pour les lignes en français smile)

Pour trouver la formule inverse, c'est à peine plus compliqué.
Il suffit de trouver sur quelle ligne il se trouve.
Lorsqu'on à la ligne L, on en déduit la colonne par: [latex]C=n-\dfrac{L(L-1)}2[/latex].
Pour trouver la ligne L(n) pour le nombre n, on remarque que:
[TeX]\dfrac{L(L-1)}2<n\le\dfrac{L(L+1)}2[/TeX]
[TeX]\dfrac{L(L-1)}2<2n \Rightarrow (L-\dfrac12)^2-\dfrac14-2n<0 \Rightarrow L<\dfrac12+sqrt{2n+\dfrac14}[/latex] (vu nos conditions de positivité)

L'égalité n'étant jamais possible (l'égalité serait vraie pour le premier nombre de la ligne suivante). De même avec l'autre inéquation on montre que:
[latex]sqrt{2n-\dfrac14}-\dfrac12 \le L<\dfrac12+sqrt{2n+\dfrac14}[/TeX]
On en déduit:
[TeX]L(n)=E(sqrt{2n-\dfrac14}+\dfrac12 )[/latex], où E(x) désigne la partie entière de x et [latex]C(n)=n-\dfrac{L(n)(L(n)-1)}2[/TeX]
Voila, voila. Merci pour avoir partagé cette énigme et comme je n'ai pas besoin de la calculatrice, je la laisse à quelqu'un d'autre smile

 #13 - 05-11-2010 17:29:29

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2123

coprdonnées dans le triangle des entiers

1. Par récurrence on démontre que:
[TeX]f(R,R) = R*(R+1)/2[/TeX]
Initialisation:
[TeX]f(1,1) = 1*(1+1)/2[/TeX]
Hérédité:
[TeX]f(R+1,R+1)= f(R,R)+R+1 = R*(R+1)/2+(R+1)= (R+1)*(R+2)/2[/TeX]
Ensuite, il vient que :
[TeX]f(R,C) = f(R-1,R-1) + C = R*(R-1)/2+C[/TeX]
2. Pour tout N, pour trouver la ligne R:
[TeX]f(R-1,R-1) < N <= f(R,R)

R^2-R < 2N <= R^2+R[/TeX]
On recherche [latex]sqrt(2N)[/latex]

La valeur arrondie à l'entier le plus proche donne R.

La colonne C vaut:
[TeX] N-R*(R-1)/2[/TeX]


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #14 - 15-11-2010 09:27:55

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 22×32×173

coordonnées dans le trianglr des entiers

Le hasard a décidé que le gagnant était Nate Burchell, sa solution :



http://wildaboutmath.com/2010/11/14/ti- … ay-winner/

 #15 - 15-11-2010 12:00:40

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Coordonnéess dans le triangle des entiers

Le même genre de petits trucs rigolos que son problème de l'an dernier sur la spirale d'entiers, j'aime bien. Etonnant, d'ailleurs, que je n'ai pas pris le temps de répondre à celui-là, moi qui me régale tant d'habitude ^^


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete