Énigme de la semaine 1

Trop de police à Métropolis !

(D’après le Championnat International des Jeux Mathématiques et Logiques)

1. La police de Métropolis est sur les dents. Le quartier des docks doit être surveillé jour et nuit. Ce quartier est composé de blocs carrés régulièrement espacés (voir plan ci-dessous). Un policier ne peut voir au-delà de la longueur d’un bloc.
On a illustré, sur le plan, quelques possibilités de surveillance.
Déterminez le nombre minimum de policiers nécessaires pour assurer une surveillance efficace.

2. À Métropolis, tous les habitants sont identifiés par un matricule. Les policiers qui contrôlent la ville se reconnaissent par le fait que leur matricule comporte trois chiffres et que le premier chiffre (à gauche) de leur matricule est strictement supérieur à la somme des deux derniers.
Quel est le nombre maximal de policiers dans cette ville ?

Solution

1. Il faut au moins 12 policiers.
2.
100 : 1
200 – 201 : 2
210 : 1
300 – 301 – 302 : 3
310 – 311 : 2
320 : 1
400 – 401 – 402 – 403 : 4
410 – 411 – 412 : 3
420 – 421 : 2
430 : 1
500 – 501 – 502 – 503 – 504 : 5
510 – 511 – 512 – 513 : 4
520 – 521 – 522 : 3
530 – 531 : 2
540 : 1
600 – 601 – 602 – 603 – 604 – 605 : 6
610 – 611 – 612 – 613 – 614 : 5
620 – 621 – 622 – 623 : 4
630 – 631 – 632 : 3
640 – 641 : 2
650 : 1
700 – 701 – 702 – 703 – 704 – 705 – 706 : 7
710 – 711 – 712 – 713 – 714 – 715 : 6
720 – 721 – 722 – 723 – 724 : 5
730 – 731 – 732 – 733 : 4
740 – 741 – 742 : 3
750 – 751 : 2
760 : 1
800 – 801 – 802 – 803 – 804 – 805 – 806 – 807 : 8
810 – 811 – 812 – 813 – 814 – 815 – 816 : 7
820 – 821 – 822 – 823 – 824 – 825 : 6
830 – 831 – 832 – 833 – 834 : 5
840 – 841 – 842 – 843 : 4
850 – 851 – 852 : 3
860 – 861 : 2
870 : 1
900 – 901 – 902 – 903 – 904 – 905 – 906 – 907 – 908 : 9
910 – 911 – 912 – 913 – 914 – 915 – 916 – 917 : 8
920 – 921 – 922 – 923 – 924 – 925 – 926 : 7
930 – 931 – 932 – 933 -934 – 935 : 6
940 – 941 – 942 – 943 – 944 : 5
950 – 951 – 952 – 953 : 4
960 – 961 – 962 : 3
970 – 971 : 2
980 : 1

Il y a au maximum 165 policiers à Métropolis.