Inscription / Connexion Nouveau Sujet
Niveau 2 *
Partager :

Joute n°118 : Les irréductibles

Posté par
godefroy_lehardi Posteur d'énigmes
18-08-13 à 14:10

Bonjour à tous,

Le célèbre truand Al Kapishi règne sur Mathville. Pour mettre un terme à ses agissements criminels, le FBI (Federal Bureau of Integration) doit recruter des policiers dignes de confiance, qu'on appellera "Les irréductibles" !

Une sélection rigoureuse est organisée parmi les policiers en activité depuis au moins un an : chaque candidat doit présenter sous forme de fraction le nombre d'arrestations qu'il a effectuées sur le nombre (entier) de ses années de service.
On suppose que le nombre d'arrestations ne dépasse jamais le nombre d'années de service.
Seules les fractions irréductibles différentes seront retenues.

Prenons par exemple tous les policiers en service depuis au plus 4 ans. Cela donne 14 fractions différentes:

\dfrac{0}{1}, \dfrac{1}{1}, \dfrac{0}{2},\dfrac{1}{2},\dfrac{2}{2}, \dfrac{0}{3}, \dfrac{1}{3},\dfrac{2}{3},\dfrac{3}{3}, \dfrac{0}{4}, \dfrac{1}{4}, \dfrac{2}{4}, \dfrac{3}{4}, \dfrac{4}{4}

Mais si on regarde bien, il n'y en a que 7 qui soient irréductibles et différentes :

\dfrac{0}{1}, \dfrac{1}{1}, \dfrac{1}{2}, \dfrac{1}{3},\dfrac{2}{3}, \dfrac{1}{4}, \dfrac{3}{4}


Question : Parmi tous les candidats ayant au plus 35 ans de service, combien le FBI pourra-t-il en engager au maximum ?

Joute n°118 : Les irréductibles

Posté par
panda_adnap
re : Joute n°118 : Les irréductibles 18-08-13 à 14:20

gagnéLe FBI peut engager au plus 385 agent

Merci pour l'énigme !

Posté par
Pepp671
re : Joute n°118 : Les irréductibles 18-08-13 à 14:20

perduBonjour godefroy_lehardi,

Merci pour cette énigme ! Voilà ma réponse :

Le FBI pourra engager au maximum 335 policiers (pas si mal que ça, en temps de crise ! lol)

Je poste le détail en dessous

Bonne journée

Posté par
masab
re : Joute n°118 : Les irréductibles 18-08-13 à 14:25

gagnéBonjour godefroy,

Parmi tous les candidats ayant au plus 35 ans de service, le FBI pourra engager au maximum 385 personnes.

Merci pour cette énigme arithmétique !

Posté par
Nofutur2
re : Joute n°118 : Les irréductibles 18-08-13 à 14:28

gagnéLe FBI pourra engager au maximum 385 policiers "irréductibles"...

Posté par
Pepp671
re : Joute n°118 : Les irréductibles 18-08-13 à 14:38

perduPour répondre à cette énigme je me suis servi du logiciel Maple. Il y a la fonction très utile gcd sous Maple qui permet de renvoyer le PGCD de deux nombres. Or, si la fraction est irréductible, le PGCD du numérateur et du dénominateur vaut 1. Grâce à deux boucles imbriquées (permettant de générer toutes les fractions possibles jusqu'à celle ayant un dénominateur égal à 35) et une condition (le PGCD des deux nombres vaut 1) j'ai donc pu générer la liste de toutes les fractions irréductibles et puis la fonction nops de Maple m'a permit de compter le nombre d'éléments de la liste générée.

J'ai donc utilisé le code suivant (en fin de message) pour répondre à cette énigme. Et le résultat exhaustif est :

[[0/1], [1/1], [1/2], [1/3], [2/3], [1/4], [3/4], [1/5], [2/5], [3/5], [4/5], [1/6], [5/6], [1/7], [2/7], [3/7], [4/7], [5/7], [6/7], [1/8], [3/8], [5/8], [7/8], [1/9], [2/9], [4/9], [5/9], [7/9], [8/9], [1/10], [3/10], [7/10], [9/10], [1/11], [2/11], [3/11], [4/11], [5/11], [6/11], [7/11], [8/11], [9/11], [10/11], [1/12], [5/12], [7/12], [11/12], [1/13], [2/13], [3/13], [4/13], [5/13], [6/13], [7/13], [8/13], [9/13], [10/13], [11/13], [12/13], [1/14], [3/14], [5/14], [9/14], [11/14], [13/14], [1/15], [2/15], [4/15], [7/15], [8/15], [11/15], [13/15], [14/15], [1/16], [3/16], [5/16], [7/16], [9/16], [11/16], [13/16], [15/16], [1/17], [2/17], [3/17], [4/17], [5/17], [6/17], [7/17], [8/17], [9/17], [10/17], [11/17], [12/17], [13/17], [14/17], [15/17], [16/17], [1/18], [5/18], [7/18], [11/18], [13/18], [17/18], [1/19], [2/19], [3/19], [4/19], [5/19], [6/19], [7/19], [8/19], [9/19], [10/19], [11/19], [12/19], [13/19], [14/19], [15/19], [16/19], [17/19], [18/19], [1/20], [3/20], [7/20], [9/20], [11/20], [13/20], [17/20], [19/20], [1/21], [2/21], [4/21], [5/21], [8/21], [10/21], [11/21], [13/21], [16/21], [17/21], [19/21], [20/21], [1/22], [3/22], [5/22], [7/22], [9/22], [13/22], [15/22], [17/22], [19/22], [21/22], [1/23], [2/23], [3/23], [4/23], [5/23], [6/23], [7/23], [8/23], [9/23], [10/23], [11/23], [12/23], [13/23], [14/23], [15/23], [16/23], [17/23], [18/23], [19/23], [20/23], [21/23], [22/23], [1/24], [5/24], [7/24], [11/24], [13/24], [17/24], [19/24], [23/24], [1/25], [2/25], [3/25], [4/25], [6/25], [7/25], [8/25], [9/25], [11/25], [12/25], [13/25], [14/25], [16/25], [17/25], [18/25], [19/25], [21/25], [22/25], [23/25], [24/25], [1/26], [3/26], [5/26], [7/26], [9/26], [11/26], [15/26], [17/26], [19/26], [21/26], [23/26], [25/26], [1/27], [2/27], [4/27], [5/27], [7/27], [8/27], [10/27], [11/27], [13/27], [14/27], [16/27], [17/27], [19/27], [20/27], [22/27], [23/27], [25/27], [26/27], [1/28], [3/28], [5/28], [9/28], [11/28], [13/28], [15/28], [17/28], [19/28], [23/28], [25/28], [27/28], [1/29], [2/29], [3/29], [4/29], [5/29], [6/29], [7/29], [8/29], [9/29], [10/29], [11/29], [12/29], [13/29], [14/29], [15/29], [16/29], [17/29], [18/29], [19/29], [20/29], [21/29], [22/29], [23/29], [24/29], [25/29], [26/29], [27/29], [28/29], [1/30], [7/30], [11/30], [13/30], [17/30], [19/30], [23/30], [29/30], [1/31], [2/31], [3/31], [4/31], [5/31], [6/31], [7/31], [8/31], [9/31], [10/31], [11/31], [12/31], [13/31], [14/31], [15/31], [16/31], [17/31], [18/31], [19/31], [20/31], [21/31], [22/31], [23/31], [24/31], [25/31], [26/31], [27/31], [28/31], [29/31], [30/31], [1/32], [3/32], [5/32], [7/32], [9/32], [11/32], [13/32], [15/32], [17/32], [19/32], [21/32], [23/32], [25/32], [27/32], [29/32], [31/32], [1/33], [2/33], [4/33], [5/33], [7/33], [8/33], [10/33], [13/33], [14/33], [16/33], [17/33], [19/33], [20/33], [23/33], [25/33], [26/33], [28/33], [29/33], [31/33], [32/33], [1/34], [3/34], [5/34], [7/34], [9/34], [11/34], [13/34], [15/34], [19/34], [21/34], [23/34], [25/34], [27/34], [29/34], [31/34], [33/34], [1/35], [2/35], [3/35], [4/35], [6/35], [8/35], [9/35], [11/35], [12/35], [13/35], [16/35], [17/35], [18/35], [19/35], [22/35], [23/35], [24/35], [26/35], [27/35], [29/35], [31/35], [32/35], [33/35], [34/35]]

(désolé, je ne sais pas bien me servir du Latex, et malgré plusieurs essais cela ne semble toujours pas fonctionner).

Encore une fois merci pour l'énigme !

Bonne journée

Joute n°118 : Les irréductibles

Posté par
Pepp671
re : Joute n°118 : Les irréductibles 18-08-13 à 14:42

perduOups, et un poisson pour moi, j'ai mal recopié mais c'est la règle, la bonne réponse est 385 et non 335.

Posté par
rschoon
re : Joute n°118 : Les irréductibles 18-08-13 à 14:55

gagnéBonjour à tous.

Le FBI pourra engager au maximum 385 policiers.

Merci pour l'énigme

Posté par
Chatof
re : Joute n°118 : Les irréductibles 18-08-13 à 15:00

gagné385

Le FBI pourra en engager 385 au maximum.

Bonjour,
et merci Godefroy_lehardi

Posté par
Chatof
re : Joute n°118 : Les irréductibles 18-08-13 à 15:16

gagnéUne solution avec Xcas    (gratuit) :
Alt-P   (pour « Prg »  « nouveau programme »  )
copier mon code (fir(n)  …   }    :; )
F9 (ou cliquez sur OK)
et sur la ligne numéroté suivante tapez :
fir(35)
ou
debug(fir(3))          (pour le faire tourner pas à pas ou debug(fir(35)))

fir(n):={
  local a,b,sol;
  sol:=[];
  pour a de 1 jusque n  faire
    pour b de 0 jusque a faire
      sol:=sol union %{b/a %};//sol est un ensemble, donc "union" n'ajoute la fraction que si elle n'appartient pas déjà à l'ensemble sol.
      fpour;
    fpour;
    retourne size(sol),sol;
  }:;

Posté par
Chatof
re : Joute n°118 : Les irréductibles 18-08-13 à 15:20

gagné sol:=%{ %};  (et non  sol:=[]; //car sol est ensemble et non une liste)

Posté par
frenicle
re : Joute n°118 : Les irréductibles 18-08-13 à 16:11

gagnéBonjour Godefroy

Je trouve 385 fractions différentes.

Merci pour la joute

Posté par
GaBuZoMeu
re : Joute n°118 : Les irréductibles 18-08-13 à 16:30

gagnéSage répond 385 :

Joute n°118 : Les irréductibles

Posté par
jose404
Joute N°118 : Les irréductibles 18-08-13 à 18:14

gagnéBonjour à tous,

J'ai trouvé 385 fractions irréductibles et différentes lorsque le dénominateur vaut au plus 35.
La liste de ces fractions est la suivante :
============================
0/1 ; 1/1 ; 1/2 ; 1/3 ; 2/3 ; 1/4 ; 3/4 ; 1/5 ; 2/5 ; 3/5 ; 4/5 ; 1/6 ; 5/6 ; 1/7 ; 2/7 ; 3/7 ; 4/7 ; 5/7 ; 6/7 ;
1/8 ; 3/8 ; 5/8 ; 7/8 ; 1/9 ; 2/9 ; 4/9 ; 5/9 ; 7/9 ; 8/9 ; 1/10 ; 3/10 ; 7/10 ; 9/10 ; 1/11 ; 2/11 ; 3/11 ; 4/11 ;  
5/11 ; 6/11 ; 7/11 ; 8/11 ; 9/11 ; 10/11 ; 1/12 ; 5/12 ; 7/12 ; 11/12 ; 1/13 ; 2/13 ; 3/13 ; 4/13 ; 5/13 ; 6/13;
7/13 ; 8/13 ; 9/13 ; 10/13 ; 11/13 ; 12/13 ; 1/14 ; 3/14 ; 5/14 ; 9/14 ; 11/14 ; 13/14 ; 1/15 ; 2/15 ; 4/15 ;  
7/15 ; 8/15 ; 11/15 ; 13/15 ; 14/15 ; 1/16 ; 3/16 ; 5/16 ; 7/16 ; 9/16 ; 11/16 ; 13/16 ; 15/16 ; 1/17 ; 2/17 ;
3/17 ; 4/17 ; 5/17 ; 6/17 ; 7/17 ; 8/17 ; 9/17 ; 10/17 ; 11/17 ; 12/17 ; 13/17 ; 14/17 ; 15/17 ; 16/17 ; 1/18 ;
5/18 ; 7/18 ; 11/18 ; 13/18 ; 17/18 ; 1/19 ; 2/19 ; 3/19 ; 4/19 ; 5/19 ; 6/19 ; 7/19 ; 8/19 ; 9/19 ; 10/19 ; 11/19 ;
12/19 ; 13/19 ; 14/19 ; 15/19 ; 16/19 ; 17/19 ; 18/19 ; 1/20 ; 3/20 ; 7/20 ; 9/20 ; 11/20 ; 13/20 ; 17/20 ; 19/20 ;
1/21 ; 2/21 ; 4/21 ; 5/21 ; 8/21 ; 10/21 ; 11/21 ; 13/21 ; 16/21 ; 17/21 ; 19/21 ; 20/21 ; 1/22 ; 3/22 ; 5/22 ;
7/22 ; 9/22 ; 13/22 ; 15/22 ; 17/22 ; 19/22 ; 21/22 ; 1/23 ; 2/23 ; 3/23 ; 4/23 ; 5/23 ; 6/23 ; 7/23 ; 8/23 ;  
9/23 ; 10/23 ; 11/23 ; 12/23 ; 13/23 ; 14/23 ; 15/23 ; 16/23 ; 17/23 ; 18/23 ; 19/23 ; 20/23 ; 21/23 ; 22/23 ;
1/24 ; 5/24 ; 7/24 ; 11/24 ; 13/24 ; 17/24 ; 19/24 ; 23/24 ; 1/25 ; 2/25 ; 3/25 ; 4/25 ; 6/25 ; 7/25 ; 8/25 ; 9/25 ;
11/25 ; 12/25 ; 13/25 ; 14/25 ; 16/25 ; 17/25 ; 18/25 ; 19/25 ; 21/25 ; 22/25 ; 23/25 ; 24/25 ; 1/26 ; 3/26 ;
5/26 ; 7/26 ; 9/26 ; 11/26 ; 15/26 ; 17/26 ; 19/26 ; 21/26 ; 23/26 ; 25/26 ; 1/27 ; 2/27 ; 4/27 ; 5/27 ; 7/27 ;
8/27 ; 10/27 ; 11/27 ; 13/27 ; 14/27 ; 16/27 ; 17/27 ; 19/27 ; 20/27 ; 22/27 ; 23/27 ; 25/27 ; 26/27 ; 1/28 ; 3/28 ;  
5/28 ; 9/28 ; 11/28 ; 13/28 ; 15/28 ; 17/28 ; 19/28 ; 23/28 ; 25/28 ; 27/28 ; 1/29 ; 2/29 ; 3/29 ; 4/29 ; 5/29 ;
6/29 ; 7/29 ; 8/29 ; 9/29 ; 10/29 ; 11/29 ; 12/29 ; 13/29 ; 14/29 ; 15/29 ; 16/29 ; 17/29 ; 18/29 ; 19/29 ;
20/29 ; 21/29 ; 22/29 ; 23/29 ; 24/29 ; 25/29 ; 26/29 ; 27/29 ; 28/29 ; 1/30 ; 7/30 ; 11/30 ; 13/30 ; 17/30 ; 19/30 ;
23/30 ; 29/30 ; 1/31 ; 2/31 ; 3/31 ; 4/31 ; 5/31 ; 6/31 ; 7/31 ; 8/31 ; 9/31 ; 10/31 ; 11/31 ; 12/31 ; 13/31 ;  
14/31 ; 15/31 ; 16/31 ; 17/31 ; 18/31 ; 19/31 ; 20/31 ; 21/31 ; 22/31 ; 23/31 ; 24/31 ; 25/31 ; 26/31 ; 27/31 ;
28/31 ; 29/31 ; 30/31 ; 1/32 ; 3/32 ; 5/32 ; 7/32 ; 9/32 ; 11/32 ; 13/32 ; 15/32 ; 17/32 ; 19/32 ; 21/32 ; 23/32 ;
25/32 ; 27/32 ; 29/32 ; 31/32 ; 1/33 ; 2/33 ; 4/33 ; 5/33 ; 7/33 ; 8/33 ; 10/33 ; 13/33 ; 14/33 ; 16/33 ; 17/33 ;
19/33 ; 20/33 ; 23/33 ; 25/33 ; 26/33 ; 28/33 ; 29/33 ; 31/33 ; 32/33 ; 1/34 ; 3/34 ; 5/34 ; 7/34 ; 9/34 ; 11/34 ;
13/34 ; 15/34 ; 19/34 ; 21/34 ; 23/34 ; 25/34 ; 27/34 ; 29/34 ; 31/34 ; 33/34 ; 1/35 ; 2/35 ; 3/35 ; 4/35 ;
6/35 ; 8/35 ; 9/35 ; 11/35 ; 12/35 ; 13/35 ; 16/35 ; 17/35 ; 18/35 ; 19/35 ; 22/35 ; 23/35 ; 24/35 ; 26/35 ; 27/35 ;
29/35 ; 31/35 ; 32/35 ; 33/35 et 34/35.
=============================

Merci pour cette joute N° 118 et bonne continuation à tous.

José alias jose404

Posté par
fontaine6140
re : Joute n°118 : Les irréductibles 18-08-13 à 18:26

gagnéBonjour Godefroy,

Le FBI doit engager 385 candidats au maximum .

Merci pour la joute

Posté par
geo3
re : Joute n°118 : Les irréductibles 18-08-13 à 19:00

gagnéBonjour
Je pense bien que cela doit faire 385
A+

Posté par
castoriginal
Joute n°118 : Les irréductibles 18-08-13 à 19:16

gagnéBonsoir,

il y a 385 candidats que le FBI pourrait engager.

amitiés

Posté par
dedef
re : Joute n°118 : Les irréductibles 18-08-13 à 19:18

gagnéBonjour,

385, cela sera-t'il suffisant?

Posté par
Pierre_D
re : Joute n°118 : Les irréductibles 18-08-13 à 19:23

perduBonjour Godefroy,

Après maints efforts, j'arrive à une conclusion :  384

Est-elle juste ? Là est la question. En attendant, merci à toi.

Posté par
dpi
re : Joute n°118 : Les irréductibles 18-08-13 à 19:37

gagnéBonjour,

Pour une fois on déroule... Merci de ne pas nous fatiguer après jamo

On trouve 385 irréductibles

Posté par
Alexique
re : Joute n°118 : Les irréductibles 18-08-13 à 19:39

gagnéBonjour,

le FBI pourra engager 385 agents au maximum.
Ça, c'est une énigme de vacances... mais merci quand même.

Joute n°118 : Les irréductibles

Posté par
mathart
recrutement du FBI 18-08-13 à 20:00

gagné385 agents maximum pourront etre recruté... enfin je crois

Posté par
plumemeteore
re : Joute n°118 : Les irréductibles 18-08-13 à 20:49

perduBonjour Godefroy.
386 (trois cent quatre-vingt-six) policiers seront au plus engagés.
Le nombre des fractions est la somme des nombres de 2 à 35 : 665.
Sauf pour le dénominateur 1, on élimine les fractions égales à 0 ou à 1, soixante-huit en tout.
Ensuite, voici les numérateurs éliminés en plus, en fonction du dénominateur :
4 : 2
6 : 2 3 4
8 : 2 4 6
9 : 3 6
10 : 2 4 5 6 8
12 : :2 3 4 6 8 9 10
14 : 2 4 6 7 8 10 12
15 : 3 5 6 9 10 12
16 : sept pairs
18 : huit pairs et trois triples impairs
20 : neuf pairs et deux quintuples impairs
21 : six triples et deux septuples
22 : dix pairs
24 : onze pairs et quatre triples impairs
25 : 5 10 15 20
26 : douze pairs ; 13
27 : huit triples
28 : treize pairs ; 7 21
30 : tout sauf 1 7 11 13 17 19 23 29 : vingt et un
32 : quinze pairs
33 : dix triples ; 11 22
34 : seize pairs ; 17
35 : six quintuples et quatre septuples
deux cent onze fractions encore éliminées
665-68-211 = 386

Posté par
derny
Joute n°118 : Les irréductibles 18-08-13 à 22:19

perduBonsoir
388

Posté par
wow1296
re : Joute n°118 : Les irréductibles 19-08-13 à 01:12

gagnéBonsoir^^

D'après moi, si seules les fractions irréductibles différentes sont acceptées, le nombre maximal de candidats que le FBI peut engager est 385 policiers

Merci pour cette énigme !

Posté par
torio
re : Joute n°118 : Les irréductibles 19-08-13 à 08:48

gagné385 candidats


A+ torio



0/1  1/35  1/34  1/33  1/32  1/31  1/30  1/29  1/28  1/27  1/26  1/25  1/24  1/23  1/22  1/21  1/20  1/19  1/18  2/35  1/17  2/33  1/16  2/31  1/15 2/29  1/14  2/27  1/13  2/25  1/12  3/35  2/23  3/34  
1/11  3/32  2/21  3/31  1/10  3/29  2/19  3/28  1/9  4/35  3/26  2/17  3/25  4/33  1/8  4/31  3/23  2/15  3/22  4/29  1/7  5/34  4/27  3/20  5/33  2/13  5/32  3/19  4/25  5/31  1/6  6/35  5/29  4/23  
3/17  5/28  2/11  5/27  3/16 4/21  5/26  6/31  1/5  7/34  6/29  5/24  4/19  7/33  3/14  5/23  7/32  2/9  7/31  5/22  8/35  3/13  7/30  4/17  5/21  6/25  7/29  8/33  1/4  9/35  8/31  7/27  6/23  5/19  
9/34  4/15  7/26  3/11  8/29  5/18  7/25  9/32  2/7  9/31  7/24  5/17  8/27  3/10  10/33  7/23  4/13  9/29  5/16  11/35  6/19  7/22  8/25  9/28  10/31  11/34  1/3  12/35  11/32  10/29  9/26  8/23  7/20  
6/17  11/31  5/14  9/25  4/11  11/30  7/19  10/27  13/35  3/8  11/29  8/21  13/34  5/13  12/31  7/18  9/23  11/28  13/33  2/5  13/32  11/27  9/22  7/17  12/29  5/12  13/31  8/19  11/26  14/33  3/7  13/30  
10/23  7/16  11/25  15/34  4/9  13/29  9/20  14/31  5/11  16/35  11/24  6/13  13/28  7/15  15/32  8/17  9/19  10/21  11/23  12/25  13/27  14/29  15/31  16/33  17/35  1/2  18/35  17/33  16/31  15/29  14/27  
13/25  12/23  11/21  10/19  9/17  17/32  8/15  15/28  7/13  13/24  19/35  6/11  17/31  11/20  16/29  5/9  19/34  14/25  9/16  13/23  17/30  4/7  19/33  15/26  11/19  18/31  7/12  17/29  10/17  13/22  16/27  
19/32  3/5  20/33  17/28  14/23  11/18  19/31  8/13  21/34  13/21  18/29  5/8  22/35  17/27  12/19  19/30  7/11  16/25  9/14  20/31  11/17  13/20  15/23  17/26  19/29  21/32  23/35  2/3  23/34  21/31  19/28  
17/25  15/22  13/19  24/35  11/16  20/29  9/13  16/23  23/33  7/10  19/27  12/17  17/24  22/31  5/7  23/32  18/25  13/18  21/29  8/11  19/26  11/15  25/34  14/19  17/23  20/27  23/31  26/35  3/4  25/33  22/29  
19/25  16/21  13/17  23/30  10/13  27/35  17/22  24/31  7/9  25/32  18/23  11/14  26/33  15/19  19/24  23/29  27/34  4/5  25/31  21/26  17/21  13/16  22/27  9/11  23/28  14/17  19/23  24/29  29/35  5/6  26/31  
21/25  16/19  27/32  11/13  28/33  17/20  23/27  29/34  6/7  25/29  19/22  13/15  20/23  27/31  7/8  29/33  22/25  15/17  23/26  31/35  8/9  25/28  17/19  26/29  9/10  28/31  19/21  29/32  10/11  31/34  21/23  
32/35  11/12  23/25  12/13  25/27  13/14  27/29  14/15  29/31  15/16  31/33  16/17  33/35  17/18  18/19  19/20  20/21  21/22  22/23  23/24  24/25  25/26  26/27  27/28  28/29  29/30  30/31  31/32  32/33  33/34  
34/35  1/1

édit Océane

Posté par
torio
re : Joute n°118 : Les irréductibles 19-08-13 à 08:51

gagnémeilleure mise en page :

385 candidats :


A+ Torio



  0/1  1/35  1/34  1/33  1/32  1/31  1/30  1/29  1/28  1/27  1/26  1/25
  1/24  1/23  1/22  1/21  1/20  1/19  1/18  2/35  1/17  2/33  1/16  2/31
  1/15  2/29  1/14  2/27  1/13  2/25  1/12  3/35  2/23  3/34  1/11  3/32
  2/21  3/31  1/10  3/29  2/19  3/28  1/9  4/35  3/26  2/17  3/25  4/33  1/8
4/31  3/23  2/15  3/22  4/29  1/7  5/34  4/27  3/20  5/33  2/13  5/32  3/19
4/25  5/31  1/6  6/35  5/29  4/23  3/17  5/28  2/11  5/27  3/16  4/21  5/26
6/31  1/5  7/34  6/29  5/24  4/19  7/33  3/14  5/23  7/32  2/9  7/31  5/22  
8/35  3/13  7/30  4/17  5/21  6/25  7/29  8/33  1/4  9/35  8/31  7/27  6/23  
5/19  9/34  4/15  7/26  3/11  8/29  5/18  7/25  9/32  2/7  9/31  7/24  5/17  
8/27  3/10  10/33  7/23  4/13  9/29  5/16  11/35  6/19  7/22  8/25  9/28  10/31
11/34  1/3  12/35  11/32  10/29  9/26  8/23  7/20  6/17  11/31  5/14  9/25  4/11
11/30  7/19  10/27  13/35  3/8  11/29  8/21  13/34  5/13  12/31  7/18  9/23  11/28
13/33  2/5  13/32  11/27  9/22  7/17  12/29  5/12  13/31  8/19  11/26  14/33  3/7  
13/30  10/23  7/16  11/25  15/34  4/9  13/29  9/20  14/31  5/11  16/35  11/24  6/13
13/28  7/15  15/32  8/17  9/19  10/21  11/23  12/25  13/27  14/29  15/31  16/33  
17/35  1/2  18/35  17/33  16/31  15/29  14/27  13/25  12/23  11/21  10/19  9/17  
17/32  8/15  15/28  7/13  13/24  19/35  6/11  17/31  11/20  16/29  5/9  19/34  14/25
  9/16  13/23  17/30  4/7  19/33  15/26  11/19  18/31  7/12  17/29  10/17  13/22  
16/27  19/32  3/5  20/33  17/28  14/23  11/18  19/31  8/13  21/34  13/21  18/29  
5/8  22/35  17/27  12/19  19/30  7/11  16/25  9/14  20/31  11/17  13/20  15/23  
17/26  19/29  21/32  23/35  2/3  23/34  21/31  19/28  17/25  15/22  13/19  24/35  
11/16  20/29  9/13  16/23  23/33  7/10  19/27  12/17  17/24  22/31  5/7  23/32  
18/25  13/18  21/29  8/11  19/26  11/15  25/34  14/19  17/23  20/27  23/31  26/35  
3/4  25/33  22/29  19/25  16/21  13/17  23/30  10/13  27/35  17/22  24/31  7/9  25/32
18/23  11/14  26/33  15/19  19/24  23/29  27/34  4/5  25/31  21/26  17/21  13/16  
22/27  9/11  23/28  14/17  19/23  24/29  29/35  5/6  26/31  21/25  16/19  27/32  
11/13  28/33  17/20  23/27  29/34  6/7  25/29  19/22  13/15  20/23  27/31  7/8
29/33  22/25  15/17  23/26  31/35  8/9  25/28  17/19  26/29  9/10  28/31  19/21
29/32  10/11  31/34  21/23  32/35  11/12  23/25  12/13  25/27  13/14  27/29  14/15
29/31  15/16  31/33  16/17  33/35  17/18  18/19  19/20  20/21  21/22  22/23  23/24
24/25  25/26  26/27  27/28  28/29  29/30  30/31  31/32  32/33  33/34  34/35  1/1

Posté par
Alishisap
re : Joute n°118 : Les irréductibles 19-08-13 à 10:46

gagnéBonjour et merci.
Le FBI pourra en engager 385 au maximum.

La programmation du problème est on ne peut plus simple : on génère les 665 fractions possibles à l'aide de 2 boucles, une pour le numérateur n et l'autre pour le dénominateur d et à chaque fois on calcule \text{PGCD}(n; d). S'il est différent de 1, la fraction est réductible. Une seule exception : 0/1 où \text{PGCD}(0; 1)=0. On met en place un compteur incrémenté à chaque fraction irréductible rencontrée et on affiche cette dernière (optionnel).

Note : le nombre N de fractions (irréductibles et réductibles) différentes en fonction du nombre maximum d'années de service n est : N=\dfrac{n(n+3)}{2}. Ainsi, pour n=4, N=14. Pour n=35, N=665.

Voici la liste des 385 fractions pour 35 années de services (irréductibles et différentes) :

0 / 1
1 / 1
1 / 2
1 / 3
2 / 3
1 / 4
3 / 4
1 / 5
2 / 5
3 / 5
4 / 5
1 / 6
5 / 6
1 / 7
2 / 7
3 / 7
4 / 7
5 / 7
6 / 7
1 / 8
3 / 8
5 / 8
7 / 8
1 / 9
2 / 9
4 / 9
5 / 9
7 / 9
8 / 9
1 / 10
3 / 10
7 / 10
9 / 10
1 / 11
2 / 11
3 / 11
4 / 11
5 / 11
6 / 11
7 / 11
8 / 11
9 / 11
10 / 11
1 / 12
5 / 12
7 / 12
11 / 12
1 / 13
2 / 13
3 / 13
4 / 13
5 / 13
6 / 13
7 / 13
8 / 13
9 / 13
10 / 13
11 / 13
12 / 13
1 / 14
3 / 14
5 / 14
9 / 14
11 / 14
13 / 14
1 / 15
2 / 15
4 / 15
7 / 15
8 / 15
11 / 15
13 / 15
14 / 15
1 / 16
3 / 16
5 / 16
7 / 16
9 / 16
11 / 16
13 / 16
15 / 16
1 / 17
2 / 17
3 / 17
4 / 17
5 / 17
6 / 17
7 / 17
8 / 17
9 / 17
10 / 17
11 / 17
12 / 17
13 / 17
14 / 17
15 / 17
16 / 17
1 / 18
5 / 18
7 / 18
11 / 18
13 / 18
17 / 18
1 / 19
2 / 19
3 / 19
4 / 19
5 / 19
6 / 19
7 / 19
8 / 19
9 / 19
10 / 19
11 / 19
12 / 19
13 / 19
14 / 19
15 / 19
16 / 19
17 / 19
18 / 19
1 / 20
3 / 20
7 / 20
9 / 20
11 / 20
13 / 20
17 / 20
19 / 20
1 / 21
2 / 21
4 / 21
5 / 21
8 / 21
10 / 21
11 / 21
13 / 21
16 / 21
17 / 21
19 / 21
20 / 21
1 / 22
3 / 22
5 / 22
7 / 22
9 / 22
13 / 22
15 / 22
17 / 22
19 / 22
21 / 22
1 / 23
2 / 23
3 / 23
4 / 23
5 / 23
6 / 23
7 / 23
8 / 23
9 / 23
10 / 23
11 / 23
12 / 23
13 / 23
14 / 23
15 / 23
16 / 23
17 / 23
18 / 23
19 / 23
20 / 23
21 / 23
22 / 23
1 / 24
5 / 24
7 / 24
11 / 24
13 / 24
17 / 24
19 / 24
23 / 24
1 / 25
2 / 25
3 / 25
4 / 25
6 / 25
7 / 25
8 / 25
9 / 25
11 / 25
12 / 25
13 / 25
14 / 25
16 / 25
17 / 25
18 / 25
19 / 25
21 / 25
22 / 25
23 / 25
24 / 25
1 / 26
3 / 26
5 / 26
7 / 26
9 / 26
11 / 26
15 / 26
17 / 26
19 / 26
21 / 26
23 / 26
25 / 26
1 / 27
2 / 27
4 / 27
5 / 27
7 / 27
8 / 27
10 / 27
11 / 27
13 / 27
14 / 27
16 / 27
17 / 27
19 / 27
20 / 27
22 / 27
23 / 27
25 / 27
26 / 27
1 / 28
3 / 28
5 / 28
9 / 28
11 / 28
13 / 28
15 / 28
17 / 28
19 / 28
23 / 28
25 / 28
27 / 28
1 / 29
2 / 29
3 / 29
4 / 29
5 / 29
6 / 29
7 / 29
8 / 29
9 / 29
10 / 29
11 / 29
12 / 29
13 / 29
14 / 29
15 / 29
16 / 29
17 / 29
18 / 29
19 / 29
20 / 29
21 / 29
22 / 29
23 / 29
24 / 29
25 / 29
26 / 29
27 / 29
28 / 29
1 / 30
7 / 30
11 / 30
13 / 30
17 / 30
19 / 30
23 / 30
29 / 30
1 / 31
2 / 31
3 / 31
4 / 31
5 / 31
6 / 31
7 / 31
8 / 31
9 / 31
10 / 31
11 / 31
12 / 31
13 / 31
14 / 31
15 / 31
16 / 31
17 / 31
18 / 31
19 / 31
20 / 31
21 / 31
22 / 31
23 / 31
24 / 31
25 / 31
26 / 31
27 / 31
28 / 31
29 / 31
30 / 31
1 / 32
3 / 32
5 / 32
7 / 32
9 / 32
11 / 32
13 / 32
15 / 32
17 / 32
19 / 32
21 / 32
23 / 32
25 / 32
27 / 32
29 / 32
31 / 32
1 / 33
2 / 33
4 / 33
5 / 33
7 / 33
8 / 33
10 / 33
13 / 33
14 / 33
16 / 33
17 / 33
19 / 33
20 / 33
23 / 33
25 / 33
26 / 33
28 / 33
29 / 33
31 / 33
32 / 33
1 / 34
3 / 34
5 / 34
7 / 34
9 / 34
11 / 34
13 / 34
15 / 34
19 / 34
21 / 34
23 / 34
25 / 34
27 / 34
29 / 34
31 / 34
33 / 34
1 / 35
2 / 35
3 / 35
4 / 35
6 / 35
8 / 35
9 / 35
11 / 35
12 / 35
13 / 35
16 / 35
17 / 35
18 / 35
19 / 35
22 / 35
23 / 35
24 / 35
26 / 35
27 / 35
29 / 35
31 / 35
32 / 35
33 / 35
34 / 35

A bientôt !

Posté par
Alishisap
re : Joute n°118 : Les irréductibles 19-08-13 à 10:52

gagnéUne remarque : parmi tous les candidats (665 au total), puisque 385 sont admissibles, alors la probabilité d'être engagé est de 58% environ, on a donc plus de chances d'être engagé que recalé.

Posté par
rijks
re : Joute n°118 : Les irréductibles 19-08-13 à 10:56

gagnéBonjour,
Je trouve 385 candidats

Posté par
keitaro57
re : Joute n°118 : Les irréductibles 19-08-13 à 23:00

gagnéLe FBI pourrait engager jusqu'à 385 candidats

Posté par
papy13
Les irréductibles 20-08-13 à 08:32

perduBonjour

Excel m'a permis de trouver 383 irréductibles

Merci pour l'énigme

Posté par
sanantonio312
re : Joute n°118 : Les irréductibles 20-08-13 à 13:04

perduBonjour,
J'en ai trouvé 384

Posté par
Trablinot
re : Joute n°118 : Les irréductibles 20-08-13 à 13:35

gagnéD'une manière un peu obscure à la main, je dirais 385, maintenant je croise les doigts, si c'est faux le résultat ne devrait pas être trop loin

Posté par
franz
re : Joute n°118 : Les irréductibles 21-08-13 à 14:30

gagné385

merci pour l'énigme

Posté par
Cpierre60
re : Joute n°118 : Les irréductibles 21-08-13 à 19:32

gagnéBonjour,
Merci pour cette énigme.
J'ai dénombré 383 fractions irréductibles  appartenant à  ]0 ; 1[ dont numérateur et dénominateur appartiennent à l'intervalle [1 ; 35] de N.
En ajoutant 0 et 1, j'arrive donc au total de

385, nombre que je propose comme réponse à l'énigme.

Posté par
brubru777
re : Joute n°118 : Les irréductibles 22-08-13 à 07:59

gagnéBonjour,

Je trouve 385 candidats potentiels.

Voici la liste de tous les candidats classés par année. On ne garde que les candidats dont le nombre d'arrestations et les années de services sont premiers entre eux.

Pour les années premières, je n'ai pas noté les candidats car il y en a (année - 1) à chaque fois.

1 an  :  2 candidats : 0/1, 1/1
2 ans :  1 candidats
3 ans :  2 candidats
4 ans :  2 candidats : 1/4, 3/4
5 ans :  4 candidats
6 ans :  2 candidats : 1/6, 5/6
7 ans :  6 candidats
8 ans :  4 candidats : 1/8, 3/8, 5/8, 7/8
9 ans :  6 candidats : 1/9, 2/9, 4/9, 5/9, 7/9, 8/9
10 ans :  4 candidats : 1/10, 3/10, 7/10, 9/10
11 ans : 10 candidats
12 ans :  4 candidats : 1/12, 5/12, 7/12, 11/12
13 ans : 12 candidats
14 ans :  6 candidats : 1/14, 3/14, 5/14, 9/14, 11/14, 13/14
15 ans :  8 candidats : 1/15, 2/15, 4/15, 7/15, 8/15, 11/15, 13/15, 14/15
16 ans :  8 candidats : 1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, 15/16
17 ans : 16 candidats
18 ans :  6 candidats : 1/18, 5/18, 7/18, 11/18, 13/18, 17/18
19 ans : 18 candidats
20 ans :  8 candidats : 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, 19/20
21 ans : 12 candidats : 1/21, 2/21, 4/21, 5/21, 8/21, 10/21, 11/21, 13/21, 16/21, 17/21, 19/21, 20/21
22 ans : 10 candidats : 1/22, 3/22, 5/22, 7/22, 9/22, 13/22, 15/22, 17/22, 19/22, 21/22
23 ans : 22 candidats
24 ans :  8 candidats : 1/24, 5/24, 7/24, 11/24, 13/24, 17/24, 19/24, 23/24
25 ans : 20 candidats : 1/25, 2/25, 3/25, 4/25, 6/25, 7/25, 8/25, 9/25, 11/25, 12/25, 13/25, 14/25, 16/25, 17/25, 18/25, 19/25, 21/25, 22/25, 23/25, 24/25
26 ans : 12 candidats : 1/26, 3/26, 5/26, 7/26, 9/26, 11/26, 15/26, 17/26, 19/26, 21/26, 23/26, 25/26
27 ans : 18 candidats : 1/27, 2/27, 4/27, 5/27, 7/27, 8/27, 10/27, 11/27, 13/27, 14/27, 16/27, 17/27, 19/27, 20/27, 22/27, 23/27, 25/27, 26/27
28 ans : 12 candidats : 1/28, 3/28, 5/28, 9/28, 11/28, 13/28, 15/28, 17/28, 19/28, 23/28, 25/28, 27/28
29 ans : 28 candidats
30 ans :  8 candidats : 1/30, 7/30, 11/30, 13/30, 17/30, 19/30, 23/30, 29/30
31 ans : 30 candidats
32 ans : 16 candidats : 1/32, 3/32, 5/32, 7/32, 9/32, 11/32, 13/32, 15/32, 17/32, 19/32, 21/32, 23/32, 25/32, 27/32, 29/32, 31/32
33 ans : 20 candidats : 1/33, 2/33, 4/33, 5/33, 7/33, 8/33, 10/33, 13/33, 14/33, 16/33, 17/33, 19/33, 20/33, 23/33, 25/33, 26/33, 28/33, 29/33, 31/33, 32/33
34 ans : 16 candidats : 1/34, 3/34, 5/34, 7/34, 9/34, 11/34, 13/34, 15/34, 19/34, 21/34, 23/34, 25/34, 27/34, 29/34, 31/34, 33/34
35 ans : 24 candidats : 1/35, 2/35, 3/35, 4/35, 6/35, 8/35, 9/35, 11/35, 12/35, 13/35, 16/35, 17/35, 18/35, 19/35, 22/35, 23/35, 24/35, 26/35, 27/35, 29/35, 31/35, 32/35, 33/35, 34/35

Total  : 385 candidats

En espérant qu'il n'y a pas d'erreur car j'ai tout fait à la main !

Merci pour l'énigme.

Posté par
LittleFox
re : Joute n°118 : Les irréductibles 22-08-13 à 09:52

gagnéLe FBI pourra engager au maximum 385 candidats.

La limite d'âge étant très petite, la force brute marche très bien. Il suffit d'énumérer toutes les fractions possibles. Pour chacune, de la réduire en calculant le PGCD au numérateur et au dénominateur. Et de l'ajouter dans la liste si elle ne s'y trouve pas déjà.

En python :

def pgcd(a,b) :
    if a < b : return pgcd(b,a)
    if b == 0 : return a
    return pgcd(b,a%b)

s = set()
for d in range(1,35+1) :
    for n in range(0,d+1) :
            p = pgcd(n,d)
            s.add((n//p,d//p))
solution = len(s)

Posté par
Raphi
re : Joute n°118 : Les irréductibles 23-08-13 à 15:25

gagnéle FBI pourra engager au maximum 385 personnes

Posté par
littleguy
re : Joute n°118 : Les irréductibles 24-08-13 à 09:36

gagnéBonjour,

Je ne suis pas sûr d'avoir bien compris le mode de fonctionnement du recrutement - ni, si c'est le cas, de mon dénombrement - mais je tente quand même : 385.

Posté par
pourlascience
ma réponse 26-08-13 à 17:35

perduBonjour et merci

390

Posté par
ksad
re : Joute n°118 : Les irréductibles 29-08-13 à 17:25

gagnéBonjour
En espérant avoir lu l'énoncé correctement (bonne résolution d'après vacances...) je propose 385 candidats (le contingent le plus important d'entre eux ayant 31 années de service).
merci pour la joute !

Posté par
albatros63
Les irréductibles 29-08-13 à 18:58

gagnéJ'en trouve 385

Bonne journée

Posté par
Aurelien_LEQUOY
Answer 30-08-13 à 18:16

gagné<?php

$annee = 35;
$elem = array();
for ($i = 1; $i <= $annee; $i++)
{
        for ($j = 0; $j <= $i; $j++)
        {
                $elem[] = $j/$i;
        }
}

echo "total : ".count($elem)."\n";
$unique = array_unique($elem);
echo "ireductible : ".count($unique)."\n";


ma réponse : 385

Posté par
seb_dji
re : Joute n°118 : Les irréductibles 03-09-13 à 12:44

gagnéje dirais 385

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°118 : Les irréductibles 09-09-13 à 08:46

Clôture de l'énigme :

Bravo à tous ceux qui ont trouvé (quelle que soit la méthode).

Posté par
frenicle
re : Joute n°118 : Les irréductibles 09-09-13 à 11:17

gagnéBonjour,

On pouvait le faire assez facilement à la main.

Notons P(n) le nombre de fractions irréductibles dont le dénominateur est au plus égal à n.
Par exemple P(4)=7 et P(35)=385.

On a P(n+1)=P(n)+\phi(n+1)\phi(n+1) désigne le nombre d'entiers inférieurs ou égaux à n+1 et premiers avec n+1 (c'est l'indicatrice d'Euler de n+1).

On a donc pour n\ge 2, P(n)=P(1)+\phi(2)+...+\phi(n)=2+\phi(2)+...+\phi(n)

Or \phi(n) est facile à calculer pour n pas trop grand.
Si p est premier, et k\ge 1, \phi(p^k)=p^k-p^{k-1}
Si n et m sont premiers entre eux, \phi(nm)=\phi(n)\phi(m)

On a donc :

\phi(2)=1,
 \\ \phi(3)=2,
 \\ \phi(4)=4-2=2,
 \\ \phi(5)=4,
 \\ \phi(6)=1\times2=2,
 \\ \phi(7)=6,
 \\ \phi(8)=8-4=4,
 \\ \phi(9)=9-3=6,
 \\ \phi(10)=1\times4=4,
 \\ \phi(11)=10,
 \\ \phi(12)=2\times2=4,
 \\ \phi(13)=12, 
 \\ \phi(14)=1\times 6=6, 
 \\ \phi(15)=2\times 4=8,
 \\ \phi(16)=16-8=8,
 \\ \phi(17)=16, 
 \\ \phi(18)=1\times 6=6,
 \\ \phi(19)=18,
 \\ \phi(20)=2\times 4=8, 
 \\ \phi(21)=2\times 6=12,
 \\ \phi(22)=1\times 10 =10,
 \\ \phi(23)=22
 \\ \phi(24)=2\times 4 = 8,
 \\ \phi(25)=25-5=20,
 \\ \phi(26)=1\times 12 = 12,
 \\ \phi(27)=27-9=18,
 \\ \phi(28)=2\times 6=12
 \\ \phi(29)=28,
 \\ \phi(30)=1\times 2\times 4=8,
 \\ \phi(31)=30,
 \\ \phi(32)=32-16=16,
 \\ \phi(33)=2\times 10=20,
 \\ \phi(34)=1\times 16=16,
 \\ \phi(35)=6\times4=24.

Donc
P(35)=2+1+2+2+4+2+6+4+6+4+10+
 \\ +4+12+6+8+8+16+6+18+8+12+10+22+8+
 \\ 20+12+18+12+28+8+30+16+20+16+24=385

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 60:40:03.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !