Défis informatiques

  • Initiateur de la discussion Initiateur de la discussion Waroc
  • Date de début Date de début
farid_h a dit:
@Waroc, je donne ma langue au chat! J'ai reflechit a une solution en decomposant a et b en facteurs primes, mais tout ca ne mene nulle part. Ou, plus probablement, je suis aveugle ou trop fatigue, tellement c'est evident.
Cliquez pour agrandir...
le raisonnement est simple, il faut appliquer la fonction ln (logarithme) ce qui donne:
a*ln(b)=b*ln(a), donc ln(a)/a = ln(b)/b
le calcul de la derivé de ln(x)/x prouve qu'elle strictement croissante de 0 -> e et strictement decroissante de e->infini
donc forcement a<e<b ou b<e<a, les seuls entiers inferieurs a e sont 1 et 2. 1 n'étant pas une solution viable il ne reste que le 2, si (2,4) est une solution alors c'est l'unique
:D
 
Waroc a dit:
le raisonnement est simple, il faut appliquer la fonction ln (logarithme) ce qui donne:
a*ln(b)=b*ln(a), donc ln(a)/a = ln(b)/b
le calcul de la derivé de ln(x)/x prouve qu'elle strictement croissante de 0 -> e et strictement decroissante de e->infini
donc forcement a<e<b ou b<e<a, les seuls entiers inferieurs a e sont 1 et 2. 1 n'étant pas une solution viable il ne reste que le 2, si (2,4) est une solution alors c'est l'unique
:D
Cliquez pour agrandir...

Mais oui, effectivement! Une preuve tres elegante. J'avais pas du tout pense aux logarithmes, et pourtant les puissances auraient du absolument montrer le chemin. Merci, ca a fait tres plaisir!
 
Waroc a dit:
le raisonnement est simple, il faut appliquer la fonction ln (logarithme) ce qui donne:
a*ln(b)=b*ln(a), donc ln(a)/a = ln(b)/b
le calcul de la derivé de ln(x)/x prouve qu'elle strictement croissante de 0 -> e et strictement decroissante de e->infini
donc forcement a<e<b ou b<e<a, les seuls entiers inferieurs a e sont 1 et 2. 1 n'étant pas une solution viable il ne reste que le 2, si (2,4) est une solution alors c'est l'unique
:D
Cliquez pour agrandir...

salam

je comprend rien du tout a ce charabia!!:p
 
Waroc a dit:
Je ne connaissais meme pas la notion de calculabilité des fonctions, j'ai demandé a wikipedia
encore une fois j'ai appris un nouveau truc grace a toi :cool:

Je vais m'y pencher dès demain matin
Cliquez pour agrandir...

Pour preciser le probleme: prouvez le theoreme suivant:

Il existe une fonction partielle f : N -...-> N qui n'est pas calculable.
 
Waroc a dit:
Il faut que tu m'aide un peu, je suis complétement largué, juste un petit indice :desole:
Cliquez pour agrandir...

Les fonctions calculables sont, entre autres, equivalentes a:
- des machines turing
- des programmes WHILE
- des programmes de registres
- des fonctions partielles mu-recursives

Il suffit donc de considerer une de ces categories, les autres sont equivalentes (ce qu'on demontre en informatique theorique).
Prenoms donc les fonctions partiells mu-recursives. En toute generalite, il faudrait considerer des functions f : N^k -...-> N,
ou bien des fonctions de strings f: (\Sigma^*)^k -...-> \Sigma^*. Mais il existe un isomorphisme entre les fonctions de strings
et celles de N^k, donc on se concentre sur celles de N^k. Grace a la fonction de Cantor, qui transforme deux chiffres un
un seul chiffre, <x,y> = "un chiffre unique qui represente x et y", on peut donc se limiter aux fonctions f: N -...-> N.

On peut toujours representer une fonctions f: N-...->N qui est partielle et mu-recursive par un string de longueur finit. A cause
de ca, on peut denombrer toutes les fonctions f: N-...->N de l'ensemble P(1) (l'ensemble des fonctions mu-recursives partielles
d'un argument) comme suit:

\psi(0): la 0-ieme fonction de P(1),
\psi(1): la 1-ere fonction de P(1),
etc...

Par exemple, \psi(0)(25) = f(25), si f est la 0-ieme fonction de P(1), si f(25) est definit.

A ce niveau la, tu peux utiliser la methode de diagonalisation pour definir une fonction qui n'est pas dans P(1).
Essayes le...
 
farid_h a dit:
Les fonctions calculables sont, entre autres, equivalentes a:
- des machines turing
- des programmes WHILE
- des programmes de registres
- des fonctions partielles mu-recursives

Il suffit donc de considerer une de ces categories, les autres sont equivalentes (ce qu'on demontre en informatique theorique).
Prenoms donc les fonctions partiells mu-recursives. En toute generalite, il faudrait considerer des functions f : N^k -...-> N,
ou bien des fonctions de strings f: (\Sigma^*)^k -...-> \Sigma^*. Mais il existe un isomorphisme entre les fonctions de strings
et celles de N^k, donc on se concentre sur celles de N^k. Grace a la fonction de Cantor, qui transforme deux chiffres un
un seul chiffre, <x,y> = "un chiffre unique qui represente x et y", on peut donc se limiter aux fonctions f: N -...-> N.

On peut toujours representer une fonctions f: N-...->N qui est partielle et mu-recursive par un string de longueur finit. A cause
de ca, on peut denombrer toutes les fonctions f: N-...->N de l'ensemble P(1) (l'ensemble des fonctions mu-recursives partielles
d'un argument) comme suit:

\psi(0): la 0-ieme fonction de P(1),
\psi(1): la 1-ere fonction de P(1),
etc...

Par exemple, \psi(0)(25) = f(25), si f est la 0-ieme fonction de P(1).

A ce niveau la, tu peux utiliser la methode de diagonalisation pour definir une fonction qui n'est pas dans P(1).
Essayes le...
Cliquez pour agrandir...
J'ai demandé juste un petit indice, la tu m'as tout expliqué :desole:
a moins que le chemin soit encore long :indigne:
 
farid_h a dit:
Les fonctions calculables sont, entre autres, equivalentes a:
- des machines turing
- des programmes WHILE
- des programmes de registres
- des fonctions partielles mu-recursives

Il suffit donc de considerer une de ces categories, les autres sont equivalentes (ce qu'on demontre en informatique theorique).
Prenoms donc les fonctions partiells mu-recursives. En toute generalite, il faudrait considerer des functions f : N^k -...-> N,
ou bien des fonctions de strings f: (\Sigma^*)^k -...-> \Sigma^*. Mais il existe un isomorphisme entre les fonctions de strings
et celles de N^k, donc on se concentre sur celles de N^k. Grace a la fonction de Cantor, qui transforme deux chiffres un
un seul chiffre, <x,y> = "un chiffre unique qui represente x et y", on peut donc se limiter aux fonctions f: N -...-> N.

On peut toujours representer une fonctions f: N-...->N qui est partielle et mu-recursive par un string de longueur finit. A cause
de ca, on peut denombrer toutes les fonctions f: N-...->N de l'ensemble P(1) (l'ensemble des fonctions mu-recursives partielles
d'un argument) comme suit:

\psi(0): la 0-ieme fonction de P(1),
\psi(1): la 1-ere fonction de P(1),
etc...

Par exemple, \psi(0)(25) = f(25), si f est la 0-ieme fonction de P(1), si f(25) est definit.

A ce niveau la, tu peux utiliser la methode de diagonalisation pour definir une fonction qui n'est pas dans P(1).
Essayes le...
Cliquez pour agrandir...

Je ne connaissais pas la méthode de diagonalisation, je viens de voir ça ,très interessant
 
Bon, pour completer le poste #188...

definissons la fonction f : N -...-> N comme:

f(k) := 0, si \psi(k)(k) = div (div, c.a.d. non-definit)
f(k) := \psi(k)(k) + 1, autrement

La fonction f ne fait pas parti de P(1), elle est incalculable, meme si elle est bien definie.
Pourquoi elle ne fait pas parti de P(1)? Supposons qu'elle en fasse parti. Dans ce cas la,
elle devrait etre dans la liste des fonctions de P(1). Disons, a la position j: f = \psi(j).

Si \psi(j)(j) = div, f(j) = 0 != div. Donc, f != \psi(j). Contradiction.
Si \psi(j)(j) est definit, f(j) = \psi(j)(j) + 1 par definition. Donc f != \psi(j) a la position j et ainsi en general. Contradiction

f est donc une nouvelle fonction qui ne fait pas parti de P(1).

En fait, il existe une infinite de fonctions non-calculables. Il suffit de les definir, par ex. comme ca:

f(k) := 0, si \psi(k)(k) = div
f(k) := \psi(k)(k) + un-autre-nombre-que-0, autrement.

Ca fait infiniment de fonctions non-calculables.

q.e.d.
 
Pour relancer le topic, un petit problème de logique:

Je dessine un cercle ayant un rayon d'1 metre .
Je jete 7 jetons dans ce cercle.
Prouvez qu'il existe au moins deux jetons séparés par une distance inférieur ou égale a 1 metre :)
 
Waroc a dit:
Pour relancer le topic, un petit problème de logique:

Je dessine un cercle ayant un rayon d'1 metre .
Je jete 7 jetons dans ce cercle.
Prouvez qu'il existe au moins deux jetons séparés par une distance inférieur ou égale a 1 metre :)
Cliquez pour agrandir...

Je me rappelle avoir lu ca quelque part dans le passe. Hmmm..., interessant!
 
Les jetons ont une distance maximale l'un de l'autre s'ils sont places comme hexagone ou heptagone regulier sur le cercle lui-meme.

Si on inscrit un hexagone regulier dans un cercle de 1m de diametre, quelle est la longueur de chaque cote? Pareil pour un heptagone regulier?

1. http://fr.wikipedia.org/wiki/Hexagone
2. http://fr.wikipedia.org/wiki/Heptagone

Dans le cas de l'hexagone, le cote a a la meme longueur que le rayon r. On peut donc jetter 6 jetons dans un cercle, et ils peuvent tous rester a 1m ou plus de distance l'un de l'autre (si ils tombent sur les points de l'hexagone regulier). Dans le cas de l'heptagone regulier, le cote a de l'heptagone = 2 \sin(\frac{\pi}{7}) r ~= 0.887r, et comme r=1m, la distance entre les points de l'heptagone est inferiere a 1m. Il est donc impossible de placer 7 jetons dans un cercle ayant tous une distance de 1m ou plus l'un de l'autre.
 
farid_h a dit:
Les jetons ont une distance maximale l'un de l'autre s'ils sont places comme hexagone ou heptagone regulier sur le cercle lui-meme.

Si on inscrit un hexagone regulier dans un cercle de 1m de diametre, quelle est la longueur de chaque cote? Pareil pour un heptagone regulier?

1. http://fr.wikipedia.org/wiki/Hexagone
2. http://fr.wikipedia.org/wiki/Heptagone

Dans le cas de l'hexagone, le cote a a la meme longueur que le rayon r. On peut donc jetter 6 jetons dans un cercle, et ils peuvent tous rester a 1m ou plus de distance l'un de l'autre (si ils tombent sur les points de l'hexagone regulier). Dans le cas de l'heptagone regulier, le cote a de l'heptagone = 2 \sin(\frac{\pi}{7}) r ~= 0.887r, et comme r=1m, la distance entre les points de l'heptagone est inferiere a 1m. Il est donc impossible de placer 7 jetons dans un cercle ayant tous une distance de 1m ou plus l'un de l'autre.
Cliquez pour agrandir...
En plaçant 6 jetons sur les sommets de l'héxagone regulier cela fonctionne et en plaçant le septième au centre, cela devrait marcher, non ? :intello:
hanae8 a dit:
ça a l'air sympa par ici !!!!!! je suis jamais venue !
Cliquez pour agrandir...
Bienvenue :D !
 
Waroc a dit:
Vous allez arrêter de bouger mes jetons svp



Donner moi une preuve un raisonnement qui tient la route
Ça se fait en 3 ligne maxi
:D
Cliquez pour agrandir...

J'ai pense a une autre solution:

Pour que la distance entre deux jetons soit 1m minimum, il faut qu'autour de chaque jeton se trouve un cercle d'un radius de 0.5m. Pour chaque jeton. Tous ces cercles doivent se trouver a l'interieur d'un grand cercle de 1.25m de radius.

Alors, la superficie d'un de ces cercles autour d'un jeton est 2*pi*(0.5^2) ~= 1.5707963 m^2
La superficie de tous ces cercles, qui ne doivent pas avoir de surface d'intersection est 6*1.5707963 ~= 9.4247778 m^2 pour 6 jetons
et 7*1.5707963 ~= 10.995574 pour 7 jetons. La superficie du grand cercle de 1.25m de diametre est 2*pi*(1.25^2) =~ 9.817477 m^2

La superficie des cercles qui sont autour des 6 jetons est 9.4247778 m^2 < 9.817477 m^2; suffisament de place donc.
La superficie des cercles qui sont autour des 7 jetons est 10.995574 m^2 > 9.817477 m^2; plus suffisament de place.

q.e.d. ? (Je ne suis pas sur que la preuve soit correcte, c'est juste une idee spontanee non-verifiee)
 
Waroc a dit:
Pour relancer le topic, un petit problème de logique:

Je dessine un cercle ayant un rayon d'1 metre .
Je jete 7 jetons dans ce cercle.
Prouvez qu'il existe au moins deux jetons séparés par une distance inférieur ou égale a 1 metre :)
Cliquez pour agrandir...
Le premier jeton est au centre.
Les 4 suivants sont disposés en croix a 90 degrés a la périphérie.

La distance entre le jeton central et chacun des autres est donc de 1 m.
La distance entre chacun des jetons périphériques est de:

√(1² + 1²) = 1.414
La plus grande distance possible pour le jeton suivant sera entre ces 2.
Cette distance est
2Rsin(45/2) soit 2 sin (22.5) = 0.7653 m

Idem pour le jeton suivant.

On a donc 2 jetons qui seront au plus a 0.7653 m d un autre.
 
@Nalinux , @farid_h les jetons sont disposés de manière aléatoire dans le cercle on ne peut donc speculer sur telle ou telle position

Le raisonnement est simple:
Je decoupe mon cercle en 6 parts de surface egale (comme une boite de fromage si vous voulez)
J'ai 7 jetons et 6 part donc il existe au moins deux points dans la meme surface
Il est facile de prouver que chaque surface est un triangle isocèle de 1m, et biensur il est evident que la distance entre deux point a l'interieur d'un triangle isocele de 1m ne peut depasser 1m

J'ai un autre probleme bcp plus difficile, perso j'ai mis 8 jours a trouver la solution, il est juste question de raisonnement et de logique ...
Si vous voulez je le partage
 
Waroc a dit:
@Nalinux , @farid_h les jetons sont disposés de manière aléatoire dans le cercle on ne peut donc speculer sur telle ou telle position

Le raisonnement est simple:
Je decoupe mon cercle en 6 parts de surface egale (comme une boite de fromage si vous voulez)
J'ai 7 jetons et 6 part donc il existe au moins deux points dans la meme surface
Il est facile de prouver que chaque surface est un triangle isocèle de 1m, et biensur il est evident que la distance entre deux point a l'interieur d'un triangle isocele de 1m ne peut depasser 1m

J'ai un autre probleme bcp plus difficile, perso j'ai mis 8 jours a trouver la solution, il est juste question de raisonnement et de logique ...
Si vous voulez je le partage
Cliquez pour agrandir...
Pas idiot, mais je crois que ton raisonnement souffre du même mal que le mien. Tout est dans le "il est facile de prouver" :)
Fait le !
Il y a une part de ressenti, difficile a mettre en équation.

Envoi la suite.

PS: pas eu la motivation de me remettre au comptage automatique, mais ça viendra.
 
Retour
Haut