Algorithme Sympatique:
Olympiades mathématiques, énigmes et défis
-
FLBP
- Habitué(e)
- Messages: 289
- Enregistré le: 25 Aoû 2017, 02:07
-
par FLBP » 30 Sep 2018, 22:51
Hello,
Lors d'un challenge de prog où on a 2 min pour faire un code qui répond aux contraintes, je suis tombé sur un exo sympa:
Soient deux fonctions :
- Code: Tout sélectionner
Fonction foo(n):
--S = 0
--pour 1 <= i <= n:
----si pgdc(i,n) == 1:
------S += 1
--retourne S
et
- Code: Tout sélectionner
Fonction bar(N):
--R = 0
--pour 1 <= i <= N:
----si i divise N:
------R += foo(i)
--retourne R
Trouver bar(N) pour N naturel
-
LB2
- Habitué(e)
- Messages: 1504
- Enregistré le: 05 Nov 2017, 17:32
-
par LB2 » 30 Sep 2018, 23:16
C'est N mais c'est pas si évident que ça à démontrer!
-
FLBP
- Habitué(e)
- Messages: 289
- Enregistré le: 25 Aoû 2017, 02:07
-
par FLBP » 30 Sep 2018, 23:21
Bien vu ! Je laisse la démonstration en énigme
-
Ben314
- Le Ben
- Messages: 21535
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 30 Sep 2018, 23:48
Salut,
Pour
fixé, si à tout entier
on associe le couple
où
alors
- L'application atterrit dans l'ensemble des couples
tels que
divise
;
et
.
- Étant donné un tel couple
, il est clair qu'il admet un unique antécédent, à savoir
.
Donc l'application est bijective et ça prouve que
c.q.f.d.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 20 invités