Toutes les positions du morpion dans un seul nombre

Savez-vous compter les poux à la mode de chez nous ?

Par

Aabu

Temps de lecture estimé : 40 minutes

Dernière mise à jour dimanche 13 décembre 2020 à 10h58

Dans un précédent billet, j’écrivais au sujet du nombre de positions différentes au morpion, à savoir 5478 (en comptant séparément les positions équivalentes). Il est facile de représenter une position graphiquement, à l’aide d’une grille, comme suit :

+---+---+---+
| X |   | O |
+---+---+---+
|   |   | X |
+---+---+---+
|   | X | O |
+---+---+---+

Cependant, ce n’est pas très compact. Peut-on faire mieux ? Et surtout peut-on représenter de manière compacte toutes les positions d’un seul coup ?

C’est à ces questions que j’apporte une réponse dans ce billet.

Représenter une position par un nombre
Un nombre pour les représenter toutes

Représenter une position par un nombre

Une représentation ternaire

La représentation graphique présentée en introduction contient pour chaque case l’information suivante : vide, contient une croix ou contient un cercle. Si on numérote les cases comme ci-dessous, il suffit de faire une liste ordonnée de neuf symboles pour représenter la position.

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+

La position présentée en introduction est alors la suivante : X.O..X.XO, où le vide est marqué par un point pour que ce soit plus lisible.

On a ainsi représenté une position par une liste de neuf symboles choisis parmi trois différents. Mais une liste de trois symboles différents… c’est tout simplement un nombre en base 3 !

On peut donc passer de la liste de symboles à un nombre grâce à la correspondance suivante :

. pour 0,
X pour 1,
O pour 2,

On représente alors la partie X.O..X.XO par le nombre en base 3 $102001012_3$ , le 3 en indice indiquant juste la base pour éviter les ambiguïtés avec la base 10 habituelle.

Stockage d’une représentation sans (trop) gâcher

Le plus grand nombre à 9 chiffres ou moins en base 3 est le suivant : $222222222_3$ , ou 19682 en base 10. Cela donne une borne supérieure aux entiers représentant des positions, bien que ce nombre lui-même ne représente pas une position valide.

Pour encoder ce nombre en binaire, il nous faut $\log_2 19682 \approx 14{,}26$ bits. Autrement dit, il faut au plus 15 bits. Le type standard le plus juste est le type uint16 (entier non signé sur 16 bits), qui nous offre même un bit en plus, et permet ainsi de stocker deux positions dans ces 16 bits.

Avec ce type de stockage assez simple, on arrive déjà à faire rentrer sans prise de tête 5478 positions dans 5478 octets. On gâche quand même 0,37 bits par position, soit environ 5% : c’est inacceptable.

Un nombre pour les représenter toutes

Dans le schéma de stockage précédent, on gâchait quelques bits, qui correspondent à des nombres inutilisés. En effet, Entre 19683 et 2¹⁵ = 32768, il y a quelques milliers de nombres inutilisés. En fait, comme 2¹⁶ = 65536, on pourrait stocker jusqu’à trois combinaisons dans ces 16 bits (car 65536/19682 fait environ 3,3), en stockant les nombres par tranches suffisamment fines.

La forme finale de cette idée, c’est de faire des tranches d’exactement la bonne taille, soit 19683. Mathématiquement, cela revient à écrire l’ensemble de toutes les positions comme un seul nombre écrit en base 19683. Comme on doit stocker 5478 positions, il aura 5478 chiffres en base 19683.

En base 10, cela fait un seul nombre… à 23523 chiffres. Il est caché ci-dessous et a été obtenu en énumérant toutes les positions puis en faisant une conversion bête et méchante.

102 998 262 357 203 153 412 050 213 692 735 645 015 378 989 217 330 728 759 646 898 021 168 944 431 570 031 240 783 856 919 205 283 417 168 637 268 465 021 723 369 275 689 000 851 860 889 672 187 626 364 605 470 099 347 441 927 840 149 292 278 039 056 368 944 479 897 046 000 669 957 110 394 832 545 393 964 793 916 956 512 920 293 033 770 707 270 686 052 279 922 259 353 183 426 004 348 285 968 646 980 354 641 329 352 489 750 901 279 002 772 959 045 199 462 195 437 976 712 073 829 804 668 244 203 289 966 354 937 070 689 720 869 787 276 646 907 423 118 067 678 175 836 900 321 521 808 068 412 411 250 394 422 153 654 266 369 600 436 600 305 546 609 595 516 914 792 208 022 310 036 924 731 311 438 422 539 057 411 878 765 585 621 671 414 093 970 094 108 152 952 108 133 908 485 489 505 145 044 076 472 460 678 940 941 508 178 270 866 885 708 439 587 309 906 528 119 033 015 051 505 653 395 718 214 527 819 775 998 789 232 450 812 658 346 906 842 622 591 105 651 233 473 429 494 527 880 596 730 969 490 814 098 127 598 263 601 613 064 993 718 368 231 091 139 400 112 761 199 584 141 845 454 178 908 565 078 950 208 318 303 622 188 347 241 034 792 717 891 472 804 025 575 512 728 210 941 710 968 777 407 326 277 487 198 005 676 501 255 668 598 318 067 364 786 550 308 921 140 181 052 005 348 308 301 870 041 925 500 077 675 920 040 170 325 002 463 360 360 923 690 817 744 372 408 303 507 762 607 468 645 906 898 982 369 475 170 519 909 201 418 887 176 479 328 952 469 534 882 446 587 632 824 946 403 645 252 486 234 656 363 774 131 041 603 928 128 589 056 096 062 257 427 675 814 648 632 952 706 390 420 802 913 343 599 476 743 710 856 429 608 081 987 682 098 348 776 265 537 902 368 079 102 717 492 946 668 403 090 554 143 779 514 675 798 523 860 096 521 224 973 727 080 155 365 117 405 454 750 756 323 849 549 004 394 613 356 092 068 220 330 838 372 164 234 148 119 775 313 994 628 569 599 069 868 778 011 310 477 079 415 640 089 385 145 387 612 624 824 746 382 102 588 638 666 028 744 902 095 756 645 660 774 296 617 821 324 784 225 759 703 873 228 769 144 643 997 832 543 837 374 607 146 328 049 399 321 993 661 947 031 236 937 084 498 004 573 904 339 006 162 630 369 203 024 882 416 447 909 190 943 904 685 399 006 705 243 599 376 424 440 331 384 741 168 974 675 470 308 123 812 656 860 692 160 246 548 032 140 334 518 128 088 708 813 591 829 663 864 316 763 902 831 700 298 595 248 817 754 731 910 381 715 243 357 001 694 136 549 736 283 772 567 033 463 701 673 936 766 375 785 138 376 196 939 095 997 295 454 351 862 547 408 759 648 382 961 194 247 243 095 758 708 201 959 209 468 376 946 497 389 008 582 385 234 995 914 761 444 918 673 597 676 327 961 475 205 546 955 279 039 857 953 995 485 767 495 760 432 207 817 043 378 328 764 870 464 585 128 525 205 031 145 042 521 013 112 164 561 299 191 960 907 993 222 169 386 185 412 795 452 867 386 452 971 928 284 548 994 146 848 533 494 960 096 762 417 419 134 934 238 269 826 305 292 576 478 268 872 730 335 527 877 605 035 505 678 263 769 466 893 245 776 118 377 606 263 988 459 806 597 348 969 755 864 993 739 734 810 022 530 393 432 057 986 930 544 924 109 880 128 018 495 570 711 763 091 060 721 840 417 336 445 835 694 423 369 493 604 888 302 852 642 041 441 189 401 610 988 146 108 714 312 471 559 753 014 465 789 166 252 646 487 886 344 621 866 277 168 022 049 874 686 484 999 437 477 369 968 439 097 198 559 135 733 297 132 483 838 239 236 964 556 496 818 949 208 992 649 385 114 071 362 480 996 729 693 304 566 468 298 377 332 665 474 834 433 576 035 047 550 069 531 358 424 793 807 801 934 140 881 199 708 754 459 161 389 693 409 122 219 885 428 716 080 722 642 713 094 224 834 969 424 089 433 999 492 048 404 181 108 773 292 169 660 165 823 058 703 098 621 283 688 818 859 960 693 387 310 663 693 576 333 005 973 902 469 139 520 501 837 902 535 357 401 612 084 266 183 192 179 049 842 447 717 760 835 773 534 262 974 506 788 282 399 448 417 469 038 962 598 936 425 650 116 804 374 456 238 374 388 568 898 330 311 274 081 524 089 858 983 432 665 559 252 857 756 728 530 596 193 662 609 884 125 932 047 409 887 977 195 029 281 012 794 451 826 728 231 726 731 581 503 601 070 120 977 746 886 102 850 436 931 560 040 098 784 678 970 170 876 757 682 254 706 382 894 404 782 704 958 219 198 052 559 154 941 040 234 146 170 177 453 184 492 654 395 811 662 654 349 303 182 158 478 789 567 653 223 533 621 736 303 208 236 197 002 894 320 822 923 341 917 087 847 799 485 574 340 458 725 812 317 260 336 521 687 375 912 174 574 913 821 385 825 378 920 131 225 538 500 801 701 167 122 230 020 363 360 805 647 303 313 128 369 572 220 997 684 311 084 870 821 177 533 789 991 896 771 228 024 070 789 755 623 843 219 133 031 625 412 050 325 206 140 591 122 581 557 997 489 064 940 277 522 994 762 170 054 674 079 546 566 623 945 365 669 854 062 090 085 691 666 807 591 897 154 691 544 462 955 653 901 466 185 022 922 443 012 048 400 177 669 499 291 393 423 930 099 881 633 775 003 284 953 402 514 618 452 505 833 546 809 608 591 464 916 287 748 401 974 942 632 216 819 465 032 153 306 971 145 755 255 763 905 451 567 679 697 608 569 112 222 236 500 679 177 551 335 633 575 354 968 028 576 006 553 634 734 767 811 444 870 066 849 651 891 003 833 143 365 385 839 730 667 329 151 668 437 704 982 195 759 126 085 268 416 332 842 473 633 167 378 802 398 426 244 277 793 657 472 102 780 463 665 550 218 275 428 652 104 488 908 835 718 593 226 726 914 950 285 212 290 285 906 995 352 464 939 153 841 042 789 005 462 500 512 054 519 102 683 840 066 009 182 631 398 049 183 351 475 297 236 783 132 953 329 255 960 306 766 884 862 812 540 804 513 771 389 516 955 596 550 113 116 422 694 649 864 751 516 389 495 631 710 614 082 560 482 785 519 268 274 552 736 776 327 518 002 093 512 286 148 308 164 134 989 603 131 574 215 744 256 471 120 963 620 175 156 433 423 673 354 155 261 734 964 346 044 622 802 048 281 906 977 520 494 236 617 385 448 623 939 794 681 184 477 644 773 954 279 640 230 658 303 367 471 992 922 491 759 099 437 646 043 626 997 389 933 551 588 749 755 356 619 758 809 421 670 282 722 101 550 708 472 138 329 853 085 517 270 262 997 527 776 618 064 128 272 425 380 718 601 841 857 737 747 530 892 113 342 326 386 011 859 960 250 932 992 969 161 728 512 534 199 223 213 413 059 806 843 687 036 850 896 286 178 093 005 014 667 576 903 233 034 818 819 116 931 926 534 996 473 303 006 907 581 936 203 183 003 175 837 354 691 640 607 186 748 214 440 746 459 773 449 295 058 072 524 835 525 892 598 055 766 626 920 863 583 566 922 567 306 360 790 310 617 547 640 501 259 162 252 118 934 783 141 748 042 745 876 913 676 191 899 975 545 326 849 403 629 747 138 433 911 026 465 723 620 118 607 749 560 822 260 654 926 437 136 418 468 621 116 832 781 377 660 546 958 791 917 839 638 872 420 598 275 533 386 758 713 946 108 852 949 615 318 041 171 866 781 014 245 610 704 734 062 561 179 150 450 500 830 031 345 707 825 502 743 286 909 463 059 191 042 388 563 031 273 019 866 204 527 328 063 730 433 246 763 359 745 966 646 899 538 291 728 672 748 344 416 589 495 867 960 048 501 305 686 506 048 341 124 020 454 714 475 399 713 366 359 689 583 013 058 603 345 765 751 134 865 490 119 694 863 974 180 778 441 998 601 912 392 339 437 171 169 130 177 982 670 300 076 885 198 748 292 244 776 865 234 742 556 608 381 159 820 799 222 500 689 087 490 187 350 650 578 299 153 688 784 084 430 323 157 043 920 564 600 327 335 613 763 324 686 894 856 762 430 080 384 672 918 756 341 196 384 100 228 545 560 786 924 011 954 445 197 113 019 464 636 930 437 493 368 173 927 925 446 940 013 245 918 569 327 912 884 867 425 259 857 065 817 770 976 317 141 113 965 972 406 629 405 713 830 706 547 040 692 582 769 472 115 972 542 432 909 801 629 101 467 163 700 914 723 713 594 653 076 691 094 863 436 401 575 099 757 500 411 247 728 581 384 349 968 024 482 864 015 422 765 637 027 089 299 161 191 915 449 689 660 613 174 005 619 131 357 748 942 018 256 520 945 874 938 414 815 084 218 600 847 345 546 275 372 126 824 937 369 856 652 554 008 655 844 245 992 396 597 676 674 690 798 972 314 491 264 958 412 084 168 366 082 190 089 603 897 984 969 477 939 074 110 749 112 633 230 857 906 467 053 642 298 349 359 724 776 678 966 782 485 731 035 662 459 199 734 399 593 028 634 003 747 614 029 535 504 967 381 613 957 838 322 974 848 943 808 152 324 165 404 423 848 217 083 508 477 252 380 133 819 117 870 391 266 129 959 113 528 743 846 356 240 952 754 506 191 024 913 365 328 470 178 508 457 569 733 274 702 775 751 370 710 813 181 080 884 934 848 298 258 650 809 283 530 613 789 520 569 399 382 598 857 828 705 721 992 003 730 287 867 882 030 883 649 165 607 362 282 285 823 588 494 268 326 291 603 305 292 581 849 458 232 162 659 832 875 946 506 443 844 556 714 972 720 127 980 655 330 838 022 685 672 388 307 357 283 047 618 641 027 435 229 939 841 082 013 631 680 980 378 725 418 155 536 185 050 385 396 223 261 456 291 573 018 122 783 073 433 784 646 384 482 230 158 605 689 043 473 247 301 885 018 041 989 823 485 941 535 555 899 043 909 960 180 339 406 608 536 359 177 449 661 623 361 886 582 071 220 093 337 132 891 596 858 010 437 564 517 690 652 379 487 283 685 116 858 791 636 290 689 359 484 165 108 154 780 949 750 720 587 873 204 992 904 010 469 160 447 898 767 448 593 642 878 135 801 868 941 242 425 680 708 044 263 568 776 295 641 781 337 257 440 402 018 784 839 760 809 858 459 796 018 206 670 150 109 044 576 561 670 648 044 970 931 720 866 686 649 308 104 635 696 575 720 392 716 832 590 768 615 636 591 621 875 009 850 532 703 786 271 111 368 135 639 557 223 903 649 945 817 614 654 484 077 629 545 022 644 203 863 002 485 346 697 421 657 165 553 184 259 662 585 452 149 970 185 183 392 417 265 076 590 134 643 923 719 209 115 735 487 054 713 053 669 789 243 051 227 977 662 029 953 393 152 209 839 555 979 951 085 837 654 153 814 912 801 540 386 791 541 392 875 616 451 898 461 845 029 983 130 675 077 372 178 313 055 841 088 949 057 248 427 675 283 050 119 716 305 806 657 064 772 244 089 946 705 426 801 682 615 008 218 652 796 090 622 409 185 564 772 123 540 677 329 733 614 678 502 609 103 977 846 989 095 820 930 397 191 833 080 990 864 677 225 790 291 392 054 536 484 980 043 121 593 399 846 510 257 585 194 507 759 023 485 920 336 741 315 748 394 452 398 406 469 466 864 468 379 950 159 399 917 743 402 170 834 017 756 500 190 324 287 902 489 674 523 040 767 281 239 025 566 141 407 081 387 517 168 257 920 292 719 201 079 301 525 487 852 473 507 065 389 392 398 527 051 771 661 494 546 931 372 261 308 200 874 359 361 373 344 877 974 867 773 080 047 985 632 620 540 322 253 523 039 539 385 356 960 416 059 407 987 317 526 207 469 211 973 362 211 317 612 419 541 085 477 493 934 116 597 672 407 789 791 646 401 017 698 020 451 458 884 539 293 713 659 316 926 991 301 420 959 967 432 625 140 084 011 648 420 718 695 709 734 817 811 465 282 750 390 868 476 816 389 922 463 653 151 228 723 477 408 362 830 631 726 609 989 980 423 330 979 645 207 761 137 884 927 775 620 159 210 743 462 487 659 361 784 271 560 603 092 043 936 711 228 998 307 807 165 847 999 696 811 004 160 567 504 289 390 702 183 904 946 852 396 728 537 342 762 389 018 290 784 738 924 390 981 843 976 295 586 366 833 524 361 507 088 991 756 793 975 629 219 797 673 142 569 280 285 233 479 266 966 343 832 338 684 991 323 070 076 598 260 117 288 485 039 386 946 275 387 213 519 252 991 298 847 116 668 296 684 212 425 262 449 417 935 271 547 101 295 865 792 329 333 815 151 569 815 198 216 213 765 768 438 170 610 620 496 168 516 061 302 696 203 901 232 404 682 484 921 604 675 263 816 828 598 044 460 173 048 356 443 714 850 660 945 164 898 382 816 077 816 389 060 606 662 769 915 257 389 173 272 384 431 035 991 827 883 046 781 274 875 451 952 274 099 653 906 468 136 030 708 774 699 399 747 726 831 751 641 833 805 310 538 112 675 277 993 785 265 105 343 308 162 372 091 641 036 531 358 964 735 891 537 117 900 852 690 525 496 775 425 116 464 467 068 504 586 581 369 324 959 062 371 951 600 971 367 416 054 507 032 826 895 330 229 794 987 751 780 889 760 198 308 286 447 405 539 983 471 766 071 774 711 429 985 028 040 780 334 889 210 775 998 725 838 627 954 808 338 435 775 436 621 981 163 815 319 455 296 245 803 196 559 602 401 030 280 365 953 912 061 559 735 537 252 571 607 247 250 350 186 926 733 053 062 561 906 817 550 845 348 899 513 250 637 101 173 612 382 520 125 177 017 469 949 722 387 378 181 313 343 690 832 078 304 700 870 898 529 049 028 311 418 386 471 869 492 077 036 494 024 249 703 390 347 163 623 910 077 018 008 100 131 655 002 819 808 732 969 070 743 999 903 742 478 746 169 517 572 530 047 320 938 080 996 685 753 387 689 405 175 542 137 424 676 061 366 381 557 147 052 722 706 857 809 480 055 379 760 207 244 197 410 562 548 402 707 205 046 121 675 570 227 892 525 529 372 140 916 896 809 435 569 070 969 312 128 968 143 108 418 123 787 516 249 898 493 814 471 177 308 803 184 053 381 943 242 925 055 539 562 241 479 688 458 070 386 014 584 477 938 157 067 993 323 147 011 823 962 629 043 062 583 308 307 589 098 797 208 718 344 255 617 926 391 376 363 574 031 832 862 337 191 062 875 059 406 517 014 028 991 893 423 633 292 933 793 755 670 962 065 427 530 739 533 541 954 745 602 446 949 607 589 026 548 726 265 991 972 986 464 718 641 932 734 146 924 046 177 985 170 281 626 516 639 131 546 004 094 140 848 787 897 594 258 936 600 845 939 053 805 862 734 146 476 317 166 369 781 808 216 372 150 195 193 799 196 834 095 556 847 367 328 426 124 572 118 175 013 111 521 797 526 147 573 333 258 963 286 110 381 317 178 724 177 288 187 049 480 704 614 136 043 772 613 658 460 303 252 386 721 672 353 066 106 165 092 984 504 530 213 033 516 617 208 681 760 873 120 954 771 826 341 859 785 439 235 107 573 866 180 521 673 702 610 184 874 693 774 711 778 500 275 460 776 613 703 750 464 467 047 886 563 424 289 623 007 539 417 602 632 208 994 522 268 734 925 631 172 798 970 180 714 045 124 726 090 709 588 879 839 774 078 379 749 809 978 904 375 826 059 086 685 046 728 083 963 839 229 840 398 140 314 495 763 311 931 453 434 612 721 995 747 783 010 269 159 169 283 630 563 049 354 695 249 754 842 081 855 974 633 826 054 481 571 605 941 577 629 629 726 693 986 748 603 439 759 288 484 637 019 490 396 241 594 743 276 418 255 210 078 845 043 508 845 847 923 747 846 890 179 684 957 331 292 784 716 151 566 329 966 398 453 736 589 083 237 012 639 163 903 457 179 643 126 765 942 166 384 415 514 976 014 252 345 896 986 071 745 447 975 610 075 118 573 194 390 860 640 866 015 712 001 108 698 374 867 700 342 441 409 252 334 224 617 253 115 813 197 677 349 304 791 315 895 180 482 358 248 840 424 120 404 988 385 231 425 047 315 901 667 925 721 447 263 205 470 701 427 703 476 453 262 274 602 678 597 580 480 732 269 695 528 275 851 289 155 843 356 048 474 595 578 425 610 164 494 320 608 640 903 272 308 970 496 136 957 183 392 015 333 277 680 694 107 175 919 642 781 944 137 702 244 352 357 907 538 390 810 901 860 990 978 613 120 897 367 272 730 559 279 585 331 385 995 588 481 575 560 290 497 315 613 156 494 561 275 796 988 372 237 278 686 193 175 250 174 541 959 759 337 237 193 910 891 792 699 223 793 201 210 653 191 344 614 234 975 021 062 358 384 746 990 629 029 558 418 434 607 250 745 886 045 528 151 957 323 658 904 790 237 975 127 803 864 936 073 062 141 052 470 588 158 500 924 747 843 723 076 721 003 571 486 335 082 214 876 778 273 999 140 441 936 823 709 955 463 221 704 625 575 027 899 919 579 166 661 396 957 507 838 245 854 586 252 719 699 323 669 520 232 537 313 310 521 969 354 941 125 636 107 862 147 235 735 758 555 640 500 294 662 103 845 227 673 762 070 647 737 031 188 432 284 472 531 077 826 555 485 690 988 249 412 675 128 986 528 555 003 599 052 494 947 818 467 527 813 401 533 420 787 809 359 114 599 920 087 159 523 291 129 977 675 186 796 745 347 327 641 427 584 514 842 296 291 260 252 467 206 702 842 161 245 529 144 518 599 151 832 932 843 444 790 821 195 634 125 984 849 554 255 565 017 364 657 214 770 053 560 374 574 555 892 938 311 262 872 370 413 337 525 840 492 426 659 790 367 470 311 300 526 044 857 144 314 710 430 390 903 289 072 087 698 568 193 542 018 494 374 351 590 793 971 917 873 083 645 243 780 635 624 358 097 802 004 998 926 422 454 637 236 539 926 098 447 911 058 290 005 297 289 063 730 014 086 651 214 207 977 371 277 299 842 968 912 398 010 297 747 165 496 453 849 465 805 405 350 177 477 142 693 672 427 624 781 128 344 288 363 347 919 257 762 314 001 033 561 525 108 717 377 560 451 298 441 380 770 974 704 662 651 228 784 529 263 296 939 836 206 776 181 574 101 706 098 772 321 828 649 613 601 723 134 336 978 253 540 249 240 953 528 532 776 356 174 826 967 665 214 416 280 272 205 209 597 126 657 973 006 314 086 590 869 088 126 382 212 803 719 118 432 903 974 986 810 835 405 015 363 530 776 892 906 313 167 406 754 403 146 044 406 537 754 605 983 901 630 988 108 031 673 873 666 493 543 972 585 322 878 707 231 314 897 167 468 923 670 708 946 917 754 515 384 023 043 937 115 690 181 558 907 924 037 053 814 868 393 124 126 207 155 636 445 505 196 989 181 657 197 869 886 426 732 010 600 881 117 153 865 138 778 378 031 611 854 293 275 604 445 108 848 141 834 970 344 957 113 991 391 054 006 044 592 271 154 766 850 335 835 187 712 074 933 583 491 477 649 229 829 864 759 057 449 647 510 226 995 749 879 100 348 253 410 841 931 093 316 755 735 212 974 508 530 005 195 723 756 868 656 842 264 553 861 058 330 442 890 569 310 508 571 063 709 698 647 105 056 699 190 057 795 573 059 381 375 401 067 303 395 075 313 902 210 527 983 216 007 235 694 578 565 492 210 535 643 157 163 700 578 450 139 775 601 159 529 609 823 599 294 358 307 594 206 496 919 547 759 387 080 527 810 304 833 220 468 475 024 178 629 706 322 438 147 973 342 656 425 324 186 713 503 266 645 730 435 081 462 394 335 442 831 630 368 509 225 161 468 849 379 229 242 083 417 896 003 351 214 851 940 673 456 519 921 695 579 411 194 335 414 191 896 261 610 500 836 104 095 877 303 386 760 982 384 910 687 184 024 449 265 385 951 982 026 202 804 375 602 014 215 515 416 265 812 679 060 214 374 620 415 176 250 327 457 311 946 395 162 801 113 004 883 410 790 199 047 179 989 651 789 436 658 342 517 442 243 262 641 217 085 771 815 479 448 963 294 851 391 159 276 872 915 140 458 716 603 997 996 881 725 402 443 010 125 908 101 118 581 736 203 216 972 562 034 061 066 446 093 881 484 340 528 059 124 720 271 600 539 939 169 898 271 350 260 858 302 261 991 702 126 052 153 008 697 998 697 706 916 824 555 288 730 329 125 689 079 341 498 367 367 758 410 405 050 820 612 542 883 974 772 267 648 509 277 476 607 663 349 335 075 044 117 680 271 979 123 156 093 761 650 183 920 721 656 087 183 254 960 933 332 918 676 909 646 685 092 423 270 694 655 994 588 518 160 724 687 305 264 666 999 722 725 051 153 898 337 451 433 621 377 633 832 066 031 328 413 067 484 738 475 893 089 674 210 750 565 370 360 566 205 607 801 314 243 316 369 175 741 459 402 469 265 020 605 815 390 699 997 755 746 507 505 187 035 094 813 057 561 227 030 675 042 794 647 807 087 442 797 889 714 158 079 636 447 220 173 103 304 356 244 570 580 702 249 362 501 121 233 337 853 946 852 394 214 471 811 260 741 713 402 511 561 619 994 214 644 195 665 474 902 629 556 759 979 902 570 272 186 339 422 881 488 986 942 090 456 779 248 860 963 450 691 523 759 675 674 204 256 727 603 290 887 135 007 659 476 673 317 178 980 699 307 988 275 123 983 418 775 452 055 368 934 577 157 196 751 761 813 477 634 533 382 722 611 127 173 074 344 241 417 169 028 164 039 086 333 185 786 742 623 957 210 477 870 564 183 658 976 300 592 070 433 902 229 442 025 087 189 011 847 554 520 614 730 073 672 095 751 970 655 773 486 207 288 311 912 858 049 393 014 722 495 662 687 187 248 294 611 349 807 529 454 556 561 319 298 351 838 590 756 361 568 601 081 194 407 164 810 792 172 848 966 889 177 215 756 141 431 126 166 698 494 058 811 839 112 485 578 406 758 768 697 826 833 447 743 204 358 020 675 803 184 875 642 349 975 409 438 580 184 654 771 700 850 653 886 870 911 754 383 116 055 208 350 467 130 926 756 894 760 632 587 984 818 875 683 075 181 445 535 129 118 092 363 891 012 988 053 520 971 648 354 802 063 897 057 551 448 130 080 039 503 369 989 754 677 387 352 314 587 356 373 659 565 135 781 687 127 899 294 244 823 122 984 200 499 500 740 801 214 274 862 692 994 194 710 225 638 155 745 643 952 900 173 122 356 586 481 337 875 836 012 649 043 526 946 791 203 984 549 059 474 104 034 762 412 312 303 780 416 387 948 395 289 580 279 782 436 036 569 127 304 253 891 281 886 726 260 913 203 445 028 704 615 996 041 507 734 105 874 259 491 788 475 271 929 337 835 356 308 836 490 530 225 944 254 170 090 211 889 953 958 401 307 997 100 243 912 033 106 391 504 559 652 652 931 307 414 483 284 943 320 314 988 300 254 993 776 723 871 912 770 008 290 397 959 460 684 222 929 863 444 811 223 421 896 714 213 199 642 137 714 306 209 417 585 428 827 340 024 415 454 161 938 197 693 644 312 911 490 981 976 601 224 734 961 680 707 074 969 988 469 486 507 527 911 346 458 470 214 302 310 668 661 728 130 048 478 986 969 474 578 775 576 325 353 344 482 550 782 964 899 617 412 870 376 129 229 060 106 174 778 717 906 553 781 120 703 449 032 199 833 964 995 034 621 926 889 118 309 736 392 123 438 597 462 269 972 268 616 169 639 962 054 879 230 233 142 159 689 354 766 726 872 087 258 489 829 254 611 705 029 621 848 784 949 731 337 509 805 022 803 198 631 466 175 523 268 254 759 988 795 280 679 526 673 707 409 673 998 125 298 395 851 494 797 582 716 636 926 787 903 736 864 526 386 080 477 668 422 506 596 783 926 694 167 798 128 735 592 881 024 545 916 036 091 448 100 056 305 059 877 847 046 079 887 028 939 784 359 098 097 714 776 479 430 689 629 140 538 661 170 667 667 663 927 142 123 271 421 896 137 058 476 555 361 836 948 614 472 517 153 848 127 064 580 953 051 113 887 242 401 280 424 427 258 976 784 684 862 453 087 916 864 922 754 175 577 717 729 245 082 581 591 743 340 210 111 908 997 000 377 294 422 284 495 349 166 832 826 147 358 274 909 575 429 418 954 575 234 051 507 311 005 704 103 953 526 391 287 335 239 362 177 912 847 003 925 881 839 342 879 248 085 700 679 259 431 173 870 542 498 309 254 049 006 582 391 357 482 713 183 238 964 510 482 048 982 618 467 226 499 529 860 594 624 399 174 858 540 676 025 812 336 348 076 159 709 005 790 370 731 487 035 153 288 507 881 915 655 998 171 374 267 645 355 300 013 381 275 519 088 775 253 364 839 849 791 049 968 809 288 569 601 682 693 270 402 293 092 329 684 348 471 527 135 027 468 171 151 051 198 593 194 101 073 472 247 043 561 582 299 685 691 877 700 833 062 325 346 684 057 350 246 666 112 273 622 574 935 986 878 725 891 144 697 310 429 260 600 471 427 872 335 623 887 314 413 981 229 730 297 417 836 379 000 753 316 209 936 107 731 141 318 854 127 160 516 687 052 032 019 619 082 418 400 026 020 532 253 155 750 755 770 485 808 983 851 964 711 437 987 787 517 061 219 192 005 322 809 084 072 349 970 129 451 054 205 948 955 010 023 849 294 136 058 277 134 498 226 033 937 794 672 559 003 395 692 547 201 672 409 493 990 217 083 231 765 497 667 887 626 100 956 918 853 470 174 729 822 813 786 715 434 826 291 380 157 193 870 975 769 916 368 668 154 230 800 893 686 308 530 560 050 411 740 938 207 513 932 922 063 248 117 380 484 757 966 170 821 955 810 359 084 453 258 950 693 243 889 081 000 269 724 499 680 843 839 841 111 517 551 029 877 337 631 504 935 404 156 560 417 461 546 305 043 739 480 006 519 865 213 342 826 498 420 265 818 138 056 045 707 486 688 695 984 776 769 546 972 284 359 879 832 645 623 899 359 319 353 412 362 467 740 577 115 185 078 141 624 942 660 284 099 644 608 185 474 007 888 629 008 132 491 550 419 133 839 456 981 339 056 624 624 871 478 466 005 728 094 468 392 242 218 193 541 056 546 402 187 944 657 423 186 877 653 260 555 390 761 442 904 110 032 954 572 107 446 341 262 921 658 883 481 480 900 045 594 702 330 680 060 893 869 799 461 240 640 126 039 797 540 483 132 613 768 125 201 951 096 821 659 683 839 197 305 136 021 153 861 199 169 194 811 654 930 032 081 095 892 350 507 733 623 287 464 474 406 782 723 014 804 078 113 552 316 585 254 891 745 556 675 583 240 425 697 603 747 686 630 606 394 801 261 983 915 760 246 857 612 139 021 324 653 943 272 605 834 562 988 220 855 009 713 654 690 520 634 238 917 868 339 859 573 759 331 215 745 590 718 983 130 561 706 484 647 567 426 203 542 755 110 404 282 129 789 748 985 633 783 972 394 516 279 151 699 655 632 529 132 995 421 423 405 808 620 696 112 752 164 133 731 711 326 509 140 353 953 301 061 769 186 316 147 180 369 496 527 974 642 040 993 518 928 755 467 630 005 312 790 621 645 622 797 938 239 341 129 798 605 796 069 743 379 809 781 018 838 235 770 788 247 125 281 365 625 774 001 694 100 671 160 689 549 148 484 958 410 282 207 931 775 183 286 096 957 808 482 355 395 029 446 790 614 506 814 598 992 498 770 758 152 227 704 720 609 882 459 597 250 203 491 169 149 669 484 727 577 406 618 389 290 950 549 093 530 990 714 017 096 343 959 648 628 267 812 934 983 423 568 981 990 019 577 211 139 206 655 387 315 576 429 683 956 606 142 520 091 951 120 928 639 007 590 821 864 283 018 328 908 749 117 154 495 167 134 016 212 031 419 946 842 359 269 648 993 727 179 455 755 105 820 671 001 157 505 979 878 628 028 414 266 969 399 112 567 769 308 530 049 484 105 186 391 571 980 846 023 318 969 126 309 341 027 741 187 680 705 844 280 841 787 456 536 842 557 951 375 470 796 477 794 130 229 074 985 633 056 155 984 894 810 981 327 894 969 282 744 239 856 221 033 684 358 129 927 275 095 823 597 469 654 817 033 188 979 346 037 422 825 608 178 342 979 275 665 758 455 472 093 389 143 100 584 400 060 247 532 096 481 339 985 321 039 703 424 754 015 741 969 773 602 991 209 394 309 904 959 805 501 153 762 487 003 024 275 517 772 309 243 165 596 604 390 073 742 317 026 647 350 760 539 528 608 117 625 189 694 610 223 837 599 605 337 810 306 183 985 365 138 690 773 573 295 616 124 580 701 708 909 775 272 202 807 446 045 750 893 115 760 943 198 878 027 101 240 224 201 364 674 704 106 793 483 825 197 664 224 373 777 265 456 276 799 042 092 665 780 097 763 467 092 400 616 615 542 570 608 414 330 384 088 587 745 701 616 565 449 408 836 823 118 285 152 164 634 365 093 602 875 205 514 019 729 181 723 500 826 590 644 456 683 692 049 925 703 990 985 968 555 394 070 539 107 668 366 635 144 640 349 331 191 311 242 547 127 672 614 840 386 384 380 228 871 008 053 990 106 906 042 580 239 410 817 768 407 987 208 145 480 824 462 556 953 573 618 610 741 035 587 792 141 265 341 945 024 116 527 521 254 483 781 299 977 145 229 611 964 575 991 659 864 819 822 053 856 242 971 009 526 022 951 339 402 844 224 737 320 402 595 290 094 594 567 912 452 137 712 430 540 466 657 949 819 784 855 639 662 839 819 969 385 120 908 155 889 048 894 551 340 002 037 055 446 742 334 474 342 503 371 343 279 086 647 274 108 954 592 973 641 832 683 023 591 838 306 873 388 221 651 336 710 431 918 148 224 388 003 264 957 576 927 590 628 817 414 117 802 306 205 756 156 396 382 164 193 539 452 875 807 971 937 878 601 725 596 977 447 535 657 829 077 219 284 443 747 571 590 110 479 658 526 003 194 786 859 217 562 729 282 902 559 470 163 752 534 179 685 678 705 286 834 910 571 719 952 258 710 362 764 089 049 765 915 027 661 621 298 583 948 895 214 027 321 252 621 381 951 202 446 368 939 223 894 948 954 822 635 813 428 046 269 848 556 756 462 850 213 283 166 034 737 191 352 550 346 936 948 129 166 792 816 830 797 820 814 659 598 053 814 502 339 264 091 328 878 406 928 275 746 495 624 696 599 085 069 635 292 204 347 607 852 440 931 988 872 671 286 439 399 810 827 958 295 584 284 918 379 999 238 057 729 683 076 226 486 981 879 505 724 702 453 831 286 244 853 883 218 511 887 905 369 977 118 617 930 338 307 122 805 618 455 155 065 189 063 788 493 870 192 583 282 278 265 339 636 138 352 879 015 109 127 788 357 145 834 304 206 059 225 187 903 506 877 169 137 389 409 825 526 078 945 742 452 486 140 865 041 483 696 243 916 989 930 187 117 380 959 428 421 666 634 920 258 961 774 045 846 396 436 493 462 624 500 246 201 342 428 145 350 712 326 890 848 663 487 991 995 784 383 869 970 256 768 435 947 900 629 112 325 862 551 833 184 664 025 931 866 248 708 804 314 194 883 458 448 816 026 618 973 424 755 073 263 013 321 441 478 993 835 502 558 344 372 188 337 624 743 102 833 876 671 233 982 245 020 579 237 972 186 263 573 092 330 162 618 044 301 708 347 551 361 043 961 945 452 676 766 983 179 650 542 960 339 587 553 816 730 322 515 497 616 412 445 932 820 688 317 342 993 312 398 718 290 340 511 154 568 453 705 143 189 189 203 799 095 926 626 992 898 729 804 585 034 722 996 146 352 963 780 242 238 938 566 263 046 221 775 953 843 771 377 336 135 472 235 422 884 292 745 383 684 537 986 768 428 694 077 140 608 472 597 678 420 978 169 488 590 398 164 855 595 472 567 134 604 009 093 438 718 120 838 968 607 931 903 784 744 779 701 619 894 497 621 451 843 793 435 687 817 043 308 094 969 888 898 711 135 542 559 781 634 962 530 308 611 566 527 001 889 621 119 933 072 640 667 626 589 800 953 330 584 211 160 547 137 149 601 527 412 621 094 141 641 597 919 236 533 425 664 103 216 294 932 853 699 267 203 497 272 943 961 527 760 937 951 439 746 600 313 599 603 745 789 079 473 326 166 662 402 119 862 036 471 764 301 775 980 157 921 872 243 437 084 363 999 983 279 806 826 442 433 733 326 132 920 159 041 375 453 510 413 980 323 280 326 125 769 873 039 751 831 009 295 219 345 593 703 691 784 280 197 594 949 593 362 930 391 013 637 763 569 046 646 042 942 082 208 319 063 694 195 554 161 061 269 771 431 211 142 806 792 210 920 029 020 153 459 134 149 209 791 671 528 625 779 251 174 784 972 888 599 310 050 552 500 277 628 502 521 909 468 756 949 476 162 932 515 657 066 012 771 728 903 103 825 357 681 783 740 718 979 637 518 823 187 908 369 607 304 026 015 615 827 943 588 283 756 056 564 699 937 907 828 927 307 977 099 782 239 072 698 945 975 331 069 564 428 783 289 435 144 591 902 637 840 060 320 562 667 854 954 803 528 557 945 514 963 053 583 164 852 996 392 964 670 770 940 222 519 815 565 112 704 604 268 263 297 347 970 014 793 179 206 425 229 154 061 964 498 817 399 038 510 291 509 532 449 806 826 175 302 270 907 470 099 767 629 844 902 709 852 112 337 934 056 836 201 083 084 564 081 168 119 909 571 263 856 649 181 376 200 239 993 377 872 603 247 067 994 724 523 134 351 520 738 143 240 830 807 054 592 536 070 721 261 726 356 824 371 465 304 932 961 716 311 558 329 845 610 133 277 503 200 235 336 390 641 020 484 581 906 478 750 565 324 821 581 060 834 988 391 960 035 709 879 499 239 432 649 766 031 361 526 474 876 299 725 063 410 140 667 269 248 722 871 025 494 404 206 371 499 817 184 349 153 204 070 229 006 871 948 493 164 719 424 007 602 617 859 273 506 427 512 800 325 448 130 114 475 122 268 083 903 905 006 182 079 950 943 431 080 182 664 343 205 724 301 341 904 962 284 362 881 020 928 961 465 850 879 295 614 707 741 802 635 458 366 235 868 365 515 093 538 008 938 190 296 390 364 069 948 736 907 123 390 031 055 971 744 648 772 147 142 422 850 782 814 982 506 065 495 273 201 154 594 359 835 900 562 684 094 361 840 730 701 870 008 827 216 259 420 095 694 677 996 342 116 016 727 988 175 861 711 317 821 740 690 732 466 893 040 165 918 884 985 824 558 474 469 210 796 205 740 924 017 776 854 911 804 523 878 979 094 405 849 695 282 601 581 424 717 114 684 839 175 137 306 355 044 539 252 561 216 597 422 065 306 103 147 453 467 824 230 494 227 969 665 843 516 162 638 521 749 109 099 977 547 336 046 482 874 082 520 426 271 122 704 241 573 412 342 988 865 877 379 490 538

Avec ça, on ne gâche (presque) rien ! Je vous épargne le calcul qui permet de le vérifier.

Voilà, vous avez toutes les positions du morpion dans un seul nombre.

Bien que compact, ça ne sert presque à rien. . Entre autres choses, on peut citer les défauts suivants :

le décodage et l’encodage est beaucoup plus complexe et coûteux que juste stocker deux positions dans un uint16, pour un gain faible d’environ 5% ;
c’est difficilement indexable (la représentation dans des uint16 se fait avec un simple tableau) ;
si on cherche la compacité maximale, il suffit de stocker un programme qui recalcule les positions (c’est rapide et le programme prend déjà deux fois moins de place).

Note : Merci à @artagis pour le soutien technique nécessaire à la réalisation de ce billet. Photo souvenir ci-dessous. Merci aussi à @Stalone… je crois.

10 commentaires

artragis, dimanche 13 décembre 2020 à 11h13

ça m’a fait pensé à cette vidéo de @micmaths

13/12/20 à 11h13

+3 -0

SpaceFox, dimanche 13 décembre 2020 à 12h05

La logique derrière ce billet me fait penser à la RFC 1924. Qui nous rappelle qu’on parlait déjà d’IPv6 en 1996 !

13/12/20 à 12h05

Les textes de SpaceFox & Lisa Refur – Un Renard en Corée – Un renard au Japon – @spacefox@mastodon.spacefox.fr

+1 -0

entwanne, dimanche 13 décembre 2020 à 18h17

Par contre je me pose une question : ta représentation à 9 chiffres en base 3 permet de représenter toutes les combinaisons possibles de rien / X / O sur une grille de 3×3, soit 3⁹ (19683) combinaisons.

Mais on sait depuis tes précédents billets qu’il n’y a que 5478 combinaisons possibles dans un jeu de morpion, on a donc une représentation dont seuls 30% des éléments correspondent à une combinaison réelle.
Partant de là, est-ce qu’il ne serait pas possible de réfléchir à une représentation plus compacte qui éviterait de perdre de l’espace pour des combinaisons impossibles ?

13/12/20 à 18h17

entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d’un code pythonique

+3 -0

Aabu, dimanche 13 décembre 2020 à 19h49
Modifié

Partant de là, est-ce qu’il ne serait pas possible de réfléchir à une représentation plus compacte qui éviterait de perdre de l’espace pour des combinaisons impossibles ?

La représentation la plus compacte que j’ai est le programme qui énumère toutes les positions, comme je l’évoque à la fin du billet. Et encore, c’est un programme que je n’ai pas cherché à écrire de manière particulièrement compacte.

La compacité maximale n’est pas super intéressante, parce que tu peux toujours ranger de la complexité dans le décodeur d’une certaine manière. En pratique, tu as un compromis entre les informations que tu stockes et celles que tu calcules et la complexité du calcul.

Dans le billet, l’information pour le décodeur est assez simple : les algorithmes pour extraire les chiffres dans les bases intéressantes, et la correspondance avec une grille de morpion. Quand on parle du programme qui énumère, il est très ad hoc, car il contient plein de connaissances sur le jeu du morpion (l’alternance des joueurs, ne pas jouer deux fois sur la même case, la définition d’une victoire, etc). Il y a sûrement de bons compromis intermédiaires.

On a un compromis similaire dans les algorithmes de compression pour la musique : un algo généraliste (genre zip) sera assez mauvais, un algo qui connaît mieux les sons musicaux (MP3 par exemple) fera mieux, et on peut compresser sous forme d’indication de partition si on connaît l’instrument qui joue (ce qu’on a en quelque sorte dans les logiciels de musique assistée par ordinateur). À chaque fois le décodeur se complexifie (et sa taille aussi en moyenne).

La question de la complexité d’une séquence est d’ailleurs très intéressante avec plein de ramifications partout, notamment au sujet de la compression, mais pas que.

Et en prime dans le cas présent, la meilleure représentation dépend aussi de ce qu’on veut faire (juste les lister, rechercher des positions, etc).

Le but du billet était surtout de faire une remarque amusante en fait. Autre remarque encore plus amusante et encore moins pratique : on a une grille 3x3, donc c’est une matrice, donc ce sont en fait 3 vecteurs dans l’espace. On pourrait donc représenter l’ensemble des grilles de morpion par des tétraèdres (possiblement dégénérés) ordonné dans l’espace selon un repère donné.

13/12/20 à 19h49
Modifié

+2 -0

anonyme, dimanche 13 décembre 2020 à 20h17

Ce serait assez cool d’imprimer ces tétraèdres en 3D en grand et mettre ça dans un hall d’un labo de cristallographie.

13/12/20 à 20h17

+7 -0

melepe, lundi 14 décembre 2020 à 15h34
Modifié

On peut faire largement mieux avec les séquences de de Bruijn. Par exemple, je peux énumérer toutes les séquences de 2 bits grâce à 0110: la première séquence (01) commence à l’indice 0, la seconde (11) à l’indice 1 etc. Pour 00, ça commence à 3 et on boucle.

On souhaite pour ce problème représenter tous les mots de 9 "trits", ce qui correspond à un mot de de Bruijn de longueur totale $3^9 = 19683$ trits. Puisque qu’un nombre de de Bruijn reste un nombre de de Bruijn quand on applique une rotation à ses chiffres, on peut commencer avec le maximum de 0 (i.e. de .) au début du nombre. On peut se convaincre que le nombre maximum de . consécutifs est exactement 9 (car sinon on aurait deux sous-mots consécutifs qui codent pour la grille vide), donc un mot qui vaut au maximum $3^{19683 - 9}$ , soit un nombre de seulement 9387 chiffres, soit un gain d’espace d’un ~~facteur de $10^{15866}$ par rapport à la solution présentée dans ce billet~~.

C’est beaucoup mieux !

Edit : on me signale que mesurer une efficacité par la taille du nombre c’est tricher, les vraies gens font ça en nombre de bits. On arrive alors à une amélioration d’un facteur 2.5, c’est bien aussi.

Et pour donner un exemple concret, voici une suite de de Bruijn de 9 trits dont la valeur est minimale (quand on le prend en temps que nombre, c’est le plus petit nombre possible) :

000 000 000 100 000 000 200 000 001 100 000 001 200 000 002 100 000 002 200 000 010 100 000 010 200 000 011 100 000 011 200 000 012 100 000 012 200 000 020 100 000 020 200 000 021 100 000 021 200 000 022 100 000 022 200 000 100 100 000 100 200 000 101 100 000 101 200 000 102 100 000 102 200 000 110 100 000 110 200 000 111 100 000 111 200 000 112 100 000 112 200 000 120 100 000 120 200 000 121 100 000 121 200 000 122 100 000 122 200 000 200 100 000 200 200 000 201 100 000 201 200 000 202 100 000 202 200 000 210 100 000 210 200 000 211 100 000 211 200 000 212 100 000 212 200 000 220 100 000 220 200 000 221 100 000 221 200 000 222 100 000 222 200 001 000 100 001 000 200 001 001 100 001 001 200 001 002 100 001 002 200 001 010 100 001 010 200 001 011 100 001 011 200 001 012 100 001 012 200 001 020 100 001 020 200 001 021 100 001 021 200 001 022 100 001 022 200 001 100 100 001 100 200 001 101 100 001 101 200 001 102 100 001 102 200 001 110 100 001 110 200 001 111 100 001 111 200 001 112 100 001 112 200 001 120 100 001 120 200 001 121 100 001 121 200 001 122 100 001 122 200 001 200 100 001 200 200 001 201 100 001 201 200 001 202 100 001 202 200 001 210 100 001 210 200 001 211 100 001 211 200 001 212 100 001 212 200 001 220 100 001 220 200 001 221 100 001 221 200 001 222 100 001 222 200 002 000 100 002 000 200 002 001 100 002 001 200 002 002 100 002 002 200 002 010 100 002 010 200 002 011 100 002 011 200 002 012 100 002 012 200 002 020 100 002 020 200 002 021 100 002 021 200 002 022 100 002 022 200 002 100 100 002 100 200 002 101 100 002 101 200 002 102 100 002 102 200 002 110 100 002 110 200 002 111 100 002 111 200 002 112 100 002 112 200 002 120 100 002 120 200 002 121 100 002 121 200 002 122 100 002 122 200 002 200 100 002 200 200 002 201 100 002 201 200 002 202 100 002 202 200 002 210 100 002 210 200 002 211 100 002 211 200 002 212 100 002 212 200 002 220 100 002 220 200 002 221 100 002 221 200 002 222 100 002 222 200 010 001 100 010 001 200 010 002 100 010 002 200 010 010 100 010 010 200 010 011 100 010 011 200 010 012 100 010 012 200 010 020 100 010 020 200 010 021 100 010 021 200 010 022 100 010 022 200 010 100 100 010 100 200 010 101 100 010 101 200 010 102 100 010 102 200 010 110 100 010 110 200 010 111 100 010 111 200 010 112 100 010 112 200 010 120 100 010 120 200 010 121 100 010 121 200 010 122 100 010 122 200 010 200 100 010 200 200 010 201 100 010 201 200 010 202 100 010 202 200 010 210 100 010 210 200 010 211 100 010 211 200 010 212 100 010 212 200 010 220 100 010 220 200 010 221 100 010 221 200 010 222 100 010 222 200 011 000 200 011 001 100 011 001 200 011 002 100 011 002 200 011 010 100 011 010 200 011 011 100 011 011 200 011 012 100 011 012 200 011 020 100 011 020 200 011 021 100 011 021 200 011 022 100 011 022 200 011 100 100 011 100 200 011 101 100 011 101 200 011 102 100 011 102 200 011 110 100 011 110 200 011 111 100 011 111 200 011 112 100 011 112 200 011 120 100 011 120 200 011 121 100 011 121 200 011 122 100 011 122 200 011 200 100 011 200 200 011 201 100 011 201 200 011 202 100 011 202 200 011 210 100 011 210 200 011 211 100 011 211 200 011 212 100 011 212 200 011 220 100 011 220 200 011 221 100 011 221 200 011 222 100 011 222 200 012 000 200 012 001 100 012 001 200 012 002 100 012 002 200 012 010 100 012 010 200 012 011 100 012 011 200 012 012 100 012 012 200 012 020 100 012 020 200 012 021 100 012 021 200 012 022 100 012 022 200 012 100 100 012 100 200 012 101 100 012 101 200 012 102 100 012 102 200 012 110 100 012 110 200 012 111 100 012 111 200 012 112 100 012 112 200 012 120 100 012 120 200 012 121 100 012 121 200 012 122 100 012 122 200 012 200 100 012 200 200 012 201 100 012 201 200 012 202 100 012 202 200 012 210 100 012 210 200 012 211 100 012 211 200 012 212 100 012 212 200 012 220 100 012 220 200 012 221 100 012 221 200 012 222 100 012 222 200 020 002 100 020 002 200 020 010 100 020 010 200 020 011 100 020 011 200 020 012 100 020 012 200 020 020 100 020 020 200 020 021 100 020 021 200 020 022 100 020 022 200 020 100 100 020 100 200 020 101 100 020 101 200 020 102 100 020 102 200 020 110 100 020 110 200 020 111 100 020 111 200 020 112 100 020 112 200 020 120 100 020 120 200 020 121 100 020 121 200 020 122 100 020 122 200 020 200 100 020 200 200 020 201 100 020 201 200 020 202 100 020 202 200 020 210 100 020 210 200 020 211 100 020 211 200 020 212 100 020 212 200 020 220 100 020 220 200 020 221 100 020 221 200 020 222 100 020 222 200 021 001 100 021 001 200 021 002 100 021 002 200 021 010 100 021 010 200 021 011 100 021 011 200 021 012 100 021 012 200 021 020 100 021 020 200 021 021 100 021 021 200 021 022 100 021 022 200 021 100 100 021 100 200 021 101 100 021 101 200 021 102 100 021 102 200 021 110 100 021 110 200 021 111 100 021 111 200 021 112 100 021 112 200 021 120 100 021 120 200 021 121 100 021 121 200 021 122 100 021 122 200 021 200 100 021 200 200 021 201 100 021 201 200 021 202 100 021 202 200 021 210 100 021 210 200 021 211 100 021 211 200 021 212 100 021 212 200 021 220 100 021 220 200 021 221 100 021 221 200 021 222 100 021 222 200 022 001 100 022 001 200 022 002 100 022 002 200 022 010 100 022 010 200 022 011 100 022 011 200 022 012 100 022 012 200 022 020 100 022 020 200 022 021 100 022 021 200 022 022 100 022 022 200 022 100 100 022 100 200 022 101 100 022 101 200 022 102 100 022 102 200 022 110 100 022 110 200 022 111 100 022 111 200 022 112 100 022 112 200 022 120 100 022 120 200 022 121 100 022 121 200 022 122 100 022 122 200 022 200 100 022 200 200 022 201 100 022 201 200 022 202 100 022 202 200 022 210 100 022 210 200 022 211 100 022 211 200 022 212 100 022 212 200 022 220 100 022 220 200 022 221 100 022 221 200 022 222 100 022 222 200 100 100 100 200 100 101 100 100 101 200 100 102 100 100 102 200 100 110 100 100 110 200 100 111 100 100 111 200 100 112 100 100 112 200 100 120 100 100 120 200 100 121 100 100 121 200 100 122 100 100 122 200 100 200 200 100 201 100 100 201 200 100 202 100 100 202 200 100 210 100 100 210 200 100 211 100 100 211 200 100 212 100 100 212 200 100 220 100 100 220 200 100 221 100 100 221 200 100 222 100 100 222 200 101 001 100 101 001 200 101 002 100 101 002 200 101 010 100 101 010 200 101 011 100 101 011 200 101 012 100 101 012 200 101 020 100 101 020 200 101 021 100 101 021 200 101 022 100 101 022 200 101 100 200 101 101 100 101 101 200 101 102 100 101 102 200 101 110 100 101 110 200 101 111 100 101 111 200 101 112 100 101 112 200 101 120 100 101 120 200 101 121 100 101 121 200 101 122 100 101 122 200 101 200 200 101 201 100 101 201 200 101 202 100 101 202 200 101 210 100 101 210 200 101 211 100 101 211 200 101 212 100 101 212 200 101 220 100 101 220 200 101 221 100 101 221 200 101 222 100 101 222 200 102 001 100 102 001 200 102 002 100 102 002 200 102 010 100 102 010 200 102 011 100 102 011 200 102 012 100 102 012 200 102 020 100 102 020 200 102 021 100 102 021 200 102 022 100 102 022 200 102 100 200 102 101 100 102 101 200 102 102 100 102 102 200 102 110 100 102 110 200 102 111 100 102 111 200 102 112 100 102 112 200 102 120 100 102 120 200 102 121 100 102 121 200 102 122 100 102 122 200 102 200 200 102 201 100 102 201 200 102 202 100 102 202 200 102 210 100 102 210 200 102 211 100 102 211 200 102 212 100 102 212 200 102 220 100 102 220 200 102 221 100 102 221 200 102 222 100 102 222 200 110 011 100 110 011 200 110 012 100 110 012 200 110 020 100 110 020 200 110 021 100 110 021 200 110 022 100 110 022 200 110 100 200 110 101 100 110 101 200 110 102 100 110 102 200 110 110 100 110 110 200 110 111 100 110 111 200 110 112 100 110 112 200 110 120 100 110 120 200 110 121 100 110 121 200 110 122 100 110 122 200 110 200 200 110 201 100 110 201 200 110 202 100 110 202 200 110 210 100 110 210 200 110 211 100 110 211 200 110 212 100 110 212 200 110 220 100 110 220 200 110 221 100 110 221 200 110 222 100 110 222 200 111 001 200 111 002 100 111 002 200 111 010 100 111 010 200 111 011 100 111 011 200 111 012 100 111 012 200 111 020 100 111 020 200 111 021 100 111 021 200 111 022 100 111 022 200 111 100 200 111 101 100 111 101 200 111 102 100 111 102 200 111 110 100 111 110 200 111 111 100 111 111 200 111 112 100 111 112 200 111 120 100 111 120 200 111 121 100 111 121 200 111 122 100 111 122 200 111 200 200 111 201 100 111 201 200 111 202 100 111 202 200 111 210 100 111 210 200 111 211 100 111 211 200 111 212 100 111 212 200 111 220 100 111 220 200 111 221 100 111 221 200 111 222 100 111 222 200 112 001 200 112 002 100 112 002 200 112 010 100 112 010 200 112 011 100 112 011 200 112 012 100 112 012 200 112 020 100 112 020 200 112 021 100 112 021 200 112 022 100 112 022 200 112 100 200 112 101 100 112 101 200 112 102 100 112 102 200 112 110 100 112 110 200 112 111 100 112 111 200 112 112 100 112 112 200 112 120 100 112 120 200 112 121 100 112 121 200 112 122 100 112 122 200 112 200 200 112 201 100 112 201 200 112 202 100 112 202 200 112 210 100 112 210 200 112 211 100 112 211 200 112 212 100 112 212 200 112 220 100 112 220 200 112 221 100 112 221 200 112 222 100 112 222 200 120 012 100 120 012 200 120 020 100 120 020 200 120 021 100 120 021 200 120 022 100 120 022 200 120 100 200 120 101 100 120 101 200 120 102 100 120 102 200 120 110 100 120 110 200 120 111 100 120 111 200 120 112 100 120 112 200 120 120 100 120 120 200 120 121 100 120 121 200 120 122 100 120 122 200 120 200 200 120 201 100 120 201 200 120 202 100 120 202 200 120 210 100 120 210 200 120 211 100 120 211 200 120 212 100 120 212 200 120 220 100 120 220 200 120 221 100 120 221 200 120 222 100 120 222 200 121 002 100 121 002 200 121 010 100 121 010 200 121 011 100 121 011 200 121 012 100 121 012 200 121 020 100 121 020 200 121 021 100 121 021 200 121 022 100 121 022 200 121 100 200 121 101 100 121 101 200 121 102 100 121 102 200 121 110 100 121 110 200 121 111 100 121 111 200 121 112 100 121 112 200 121 120 100 121 120 200 121 121 100 121 121 200 121 122 100 121 122 200 121 200 200 121 201 100 121 201 200 121 202 100 121 202 200 121 210 100 121 210 200 121 211 100 121 211 200 121 212 100 121 212 200 121 220 100 121 220 200 121 221 100 121 221 200 121 222 100 121 222 200 122 002 100 122 002 200 122 010 100 122 010 200 122 011 100 122 011 200 122 012 100 122 012 200 122 020 100 122 020 200 122 021 100 122 021 200 122 022 100 122 022 200 122 100 200 122 101 100 122 101 200 122 102 100 122 102 200 122 110 100 122 110 200 122 111 100 122 111 200 122 112 100 122 112 200 122 120 100 122 120 200 122 121 100 122 121 200 122 122 100 122 122 200 122 200 200 122 201 100 122 201 200 122 202 100 122 202 200 122 210 100 122 210 200 122 211 100 122 211 200 122 212 100 122 212 200 122 220 100 122 220 200 122 221 100 122 221 200 122 222 100 122 222 200 200 200 201 100 200 201 200 200 202 100 200 202 200 200 210 100 200 210 200 200 211 100 200 211 200 200 212 100 200 212 200 200 220 100 200 220 200 200 221 100 200 221 200 200 222 100 200 222 200 201 002 100 201 002 200 201 010 100 201 010 200 201 011 100 201 011 200 201 012 100 201 012 200 201 020 100 201 020 200 201 021 100 201 021 200 201 022 100 201 022 200 201 101 100 201 101 200 201 102 100 201 102 200 201 110 100 201 110 200 201 111 100 201 111 200 201 112 100 201 112 200 201 120 100 201 120 200 201 121 100 201 121 200 201 122 100 201 122 200 201 201 100 201 201 200 201 202 100 201 202 200 201 210 100 201 210 200 201 211 100 201 211 200 201 212 100 201 212 200 201 220 100 201 220 200 201 221 100 201 221 200 201 222 100 201 222 200 202 002 100 202 002 200 202 010 100 202 010 200 202 011 100 202 011 200 202 012 100 202 012 200 202 020 100 202 020 200 202 021 100 202 021 200 202 022 100 202 022 200 202 101 100 202 101 200 202 102 100 202 102 200 202 110 100 202 110 200 202 111 100 202 111 200 202 112 100 202 112 200 202 120 100 202 120 200 202 121 100 202 121 200 202 122 100 202 122 200 202 201 100 202 201 200 202 202 100 202 202 200 202 210 100 202 210 200 202 211 100 202 211 200 202 212 100 202 212 200 202 220 100 202 220 200 202 221 100 202 221 200 202 222 100 202 222 200 210 021 100 210 021 200 210 022 100 210 022 200 210 101 100 210 101 200 210 102 100 210 102 200 210 110 100 210 110 200 210 111 100 210 111 200 210 112 100 210 112 200 210 120 100 210 120 200 210 121 100 210 121 200 210 122 100 210 122 200 210 201 100 210 201 200 210 202 100 210 202 200 210 210 100 210 210 200 210 211 100 210 211 200 210 212 100 210 212 200 210 220 100 210 220 200 210 221 100 210 221 200 210 222 100 210 222 200 211 002 200 211 010 100 211 010 200 211 011 100 211 011 200 211 012 100 211 012 200 211 020 100 211 020 200 211 021 100 211 021 200 211 022 100 211 022 200 211 101 100 211 101 200 211 102 100 211 102 200 211 110 100 211 110 200 211 111 100 211 111 200 211 112 100 211 112 200 211 120 100 211 120 200 211 121 100 211 121 200 211 122 100 211 122 200 211 201 100 211 201 200 211 202 100 211 202 200 211 210 100 211 210 200 211 211 100 211 211 200 211 212 100 211 212 200 211 220 100 211 220 200 211 221 100 211 221 200 211 222 100 211 222 200 212 002 200 212 010 100 212 010 200 212 011 100 212 011 200 212 012 100 212 012 200 212 020 100 212 020 200 212 021 100 212 021 200 212 022 100 212 022 200 212 101 100 212 101 200 212 102 100 212 102 200 212 110 100 212 110 200 212 111 100 212 111 200 212 112 100 212 112 200 212 120 100 212 120 200 212 121 100 212 121 200 212 122 100 212 122 200 212 201 100 212 201 200 212 202 100 212 202 200 212 210 100 212 210 200 212 211 100 212 211 200 212 212 100 212 212 200 212 220 100 212 220 200 212 221 100 212 221 200 212 222 100 212 222 200 220 022 100 220 022 200 220 101 100 220 101 200 220 102 100 220 102 200 220 110 100 220 110 200 220 111 100 220 111 200 220 112 100 220 112 200 220 120 100 220 120 200 220 121 100 220 121 200 220 122 100 220 122 200 220 201 100 220 201 200 220 202 100 220 202 200 220 210 100 220 210 200 220 211 100 220 211 200 220 212 100 220 212 200 220 220 100 220 220 200 220 221 100 220 221 200 220 222 100 220 222 200 221 010 100 221 010 200 221 011 100 221 011 200 221 012 100 221 012 200 221 020 100 221 020 200 221 021 100 221 021 200 221 022 100 221 022 200 221 101 100 221 101 200 221 102 100 221 102 200 221 110 100 221 110 200 221 111 100 221 111 200 221 112 100 221 112 200 221 120 100 221 120 200 221 121 100 221 121 200 221 122 100 221 122 200 221 201 100 221 201 200 221 202 100 221 202 200 221 210 100 221 210 200 221 211 100 221 211 200 221 212 100 221 212 200 221 220 100 221 220 200 221 221 100 221 221 200 221 222 100 221 222 200 222 010 100 222 010 200 222 011 100 222 011 200 222 012 100 222 012 200 222 020 100 222 020 200 222 021 100 222 021 200 222 022 100 222 022 200 222 101 100 222 101 200 222 102 100 222 102 200 222 110 100 222 110 200 222 111 100 222 111 200 222 112 100 222 112 200 222 120 100 222 120 200 222 121 100 222 121 200 222 122 100 222 122 200 222 201 100 222 201 200 222 202 100 222 202 200 222 210 100 222 210 200 222 211 100 222 211 200 222 212 100 222 212 200 222 220 100 222 220 200 222 221 100 222 221 200 222 222 100 222 222 201 010 101 101 010 101 201 010 102 101 010 102 201 010 110 201 010 111 101 010 111 201 010 112 101 010 112 201 010 120 201 010 121 101 010 121 201 010 122 101 010 122 201 010 201 101 010 201 201 010 202 101 010 202 201 010 210 201 010 211 101 010 211 201 010 212 101 010 212 201 010 220 201 010 221 101 010 221 201 010 222 101 010 222 201 011 010 201 011 011 101 011 011 201 011 012 101 011 012 201 011 020 201 011 021 101 011 021 201 011 022 101 011 022 201 011 101 101 011 101 201 011 102 101 011 102 201 011 110 201 011 111 101 011 111 201 011 112 101 011 112 201 011 120 201 011 121 101 011 121 201 011 122 101 011 122 201 011 201 101 011 201 201 011 202 101 011 202 201 011 210 201 011 211 101 011 211 201 011 212 101 011 212 201 011 220 201 011 221 101 011 221 201 011 222 101 011 222 201 012 010 201 012 011 101 012 011 201 012 012 101 012 012 201 012 020 201 012 021 101 012 021 201 012 022 101 012 022 201 012 101 101 012 101 201 012 102 101 012 102 201 012 110 201 012 111 101 012 111 201 012 112 101 012 112 201 012 120 201 012 121 101 012 121 201 012 122 101 012 122 201 012 201 101 012 201 201 012 202 101 012 202 201 012 210 201 012 211 101 012 211 201 012 212 101 012 212 201 012 220 201 012 221 101 012 221 201 012 222 101 012 222 201 020 102 101 020 102 201 020 110 201 020 111 101 020 111 201 020 112 101 020 112 201 020 120 201 020 121 101 020 121 201 020 122 101 020 122 201 020 201 101 020 201 201 020 202 101 020 202 201 020 210 201 020 211 101 020 211 201 020 212 101 020 212 201 020 220 201 020 221 101 020 221 201 020 222 101 020 222 201 021 011 101 021 011 201 021 012 101 021 012 201 021 020 201 021 021 101 021 021 201 021 022 101 021 022 201 021 101 101 021 101 201 021 102 101 021 102 201 021 110 201 021 111 101 021 111 201 021 112 101 021 112 201 021 120 201 021 121 101 021 121 201 021 122 101 021 122 201 021 201 101 021 201 201 021 202 101 021 202 201 021 210 201 021 211 101 021 211 201 021 212 101 021 212 201 021 220 201 021 221 101 021 221 201 021 222 101 021 222 201 022 011 101 022 011 201 022 012 101 022 012 201 022 020 201 022 021 101 022 021 201 022 022 101 022 022 201 022 101 101 022 101 201 022 102 101 022 102 201 022 110 201 022 111 101 022 111 201 022 112 101 022 112 201 022 120 201 022 121 101 022 121 201 022 122 101 022 122 201 022 201 101 022 201 201 022 202 101 022 202 201 022 210 201 022 211 101 022 211 201 022 212 101 022 212 201 022 220 201 022 221 101 022 221 201 022 222 101 022 222 201 101 101 101 201 101 102 101 101 102 201 101 110 201 101 111 101 101 111 201 101 112 101 101 112 201 101 120 201 101 121 101 101 121 201 101 122 101 101 122 201 101 201 201 101 202 101 101 202 201 101 210 201 101 211 101 101 211 201 101 212 101 101 212 201 101 220 201 101 221 101 101 221 201 101 222 101 101 222 201 102 011 101 102 011 201 102 012 101 102 012 201 102 020 201 102 021 101 102 021 201 102 022 101 102 022 201 102 101 201 102 102 101 102 102 201 102 110 201 102 111 101 102 111 201 102 112 101 102 112 201 102 120 201 102 121 101 102 121 201 102 122 101 102 122 201 102 201 201 102 202 101 102 202 201 102 210 201 102 211 101 102 211 201 102 212 101 102 212 201 102 220 201 102 221 101 102 221 201 102 222 101 102 222 201 110 111 101 110 111 201 110 112 101 110 112 201 110 120 201 110 121 101 110 121 201 110 122 101 110 122 201 110 201 201 110 202 101 110 202 201 110 210 201 110 211 101 110 211 201 110 212 101 110 212 201 110 220 201 110 221 101 110 221 201 110 222 101 110 222 201 111 011 201 111 012 101 111 012 201 111 020 201 111 021 101 111 021 201 111 022 101 111 022 201 111 101 201 111 102 101 111 102 201 111 110 201 111 111 101 111 111 201 111 112 101 111 112 201 111 120 201 111 121 101 111 121 201 111 122 101 111 122 201 111 201 201 111 202 101 111 202 201 111 210 201 111 211 101 111 211 201 111 212 101 111 212 201 111 220 201 111 221 101 111 221 201 111 222 101 111 222 201 112 011 201 112 012 101 112 012 201 112 020 201 112 021 101 112 021 201 112 022 101 112 022 201 112 101 201 112 102 101 112 102 201 112 110 201 112 111 101 112 111 201 112 112 101 112 112 201 112 120 201 112 121 101 112 121 201 112 122 101 112 122 201 112 201 201 112 202 101 112 202 201 112 210 201 112 211 101 112 211 201 112 212 101 112 212 201 112 220 201 112 221 101 112 221 201 112 222 101 112 222 201 120 112 101 120 112 201 120 120 201 120 121 101 120 121 201 120 122 101 120 122 201 120 201 201 120 202 101 120 202 201 120 210 201 120 211 101 120 211 201 120 212 101 120 212 201 120 220 201 120 221 101 120 221 201 120 222 101 120 222 201 121 012 101 121 012 201 121 020 201 121 021 101 121 021 201 121 022 101 121 022 201 121 101 201 121 102 101 121 102 201 121 110 201 121 111 101 121 111 201 121 112 101 121 112 201 121 120 201 121 121 101 121 121 201 121 122 101 121 122 201 121 201 201 121 202 101 121 202 201 121 210 201 121 211 101 121 211 201 121 212 101 121 212 201 121 220 201 121 221 101 121 221 201 121 222 101 121 222 201 122 012 101 122 012 201 122 020 201 122 021 101 122 021 201 122 022 101 122 022 201 122 101 201 122 102 101 122 102 201 122 110 201 122 111 101 122 111 201 122 112 101 122 112 201 122 120 201 122 121 101 122 121 201 122 122 101 122 122 201 122 201 201 122 202 101 122 202 201 122 210 201 122 211 101 122 211 201 122 212 101 122 212 201 122 220 201 122 221 101 122 221 201 122 222 101 122 222 201 201 201 202 101 201 202 201 201 210 201 201 211 101 201 211 201 201 212 101 201 212 201 201 220 201 201 221 101 201 221 201 201 222 101 201 222 201 202 012 101 202 012 201 202 020 201 202 021 101 202 021 201 202 022 101 202 022 201 202 102 101 202 102 201 202 110 201 202 111 101 202 111 201 202 112 101 202 112 201 202 120 201 202 121 101 202 121 201 202 122 101 202 122 201 202 202 101 202 202 201 202 210 201 202 211 101 202 211 201 202 212 101 202 212 201 202 220 201 202 221 101 202 221 201 202 222 101 202 222 201 210 121 101 210 121 201 210 122 101 210 122 201 210 202 101 210 202 201 210 210 201 210 211 101 210 211 201 210 212 101 210 212 201 210 220 201 210 221 101 210 221 201 210 222 101 210 222 201 211 012 201 211 020 201 211 021 101 211 021 201 211 022 101 211 022 201 211 102 101 211 102 201 211 110 201 211 111 101 211 111 201 211 112 101 211 112 201 211 120 201 211 121 101 211 121 201 211 122 101 211 122 201 211 202 101 211 202 201 211 210 201 211 211 101 211 211 201 211 212 101 211 212 201 211 220 201 211 221 101 211 221 201 211 222 101 211 222 201 212 012 201 212 020 201 212 021 101 212 021 201 212 022 101 212 022 201 212 102 101 212 102 201 212 110 201 212 111 101 212 111 201 212 112 101 212 112 201 212 120 201 212 121 101 212 121 201 212 122 101 212 122 201 212 202 101 212 202 201 212 210 201 212 211 101 212 211 201 212 212 101 212 212 201 212 220 201 212 221 101 212 221 201 212 222 101 212 222 201 220 122 101 220 122 201 220 202 101 220 202 201 220 210 201 220 211 101 220 211 201 220 212 101 220 212 201 220 220 201 220 221 101 220 221 201 220 222 101 220 222 201 221 020 201 221 021 101 221 021 201 221 022 101 221 022 201 221 102 101 221 102 201 221 110 201 221 111 101 221 111 201 221 112 101 221 112 201 221 120 201 221 121 101 221 121 201 221 122 101 221 122 201 221 202 101 221 202 201 221 210 201 221 211 101 221 211 201 221 212 101 221 212 201 221 220 201 221 221 101 221 221 201 221 222 101 221 222 201 222 020 201 222 021 101 222 021 201 222 022 101 222 022 201 222 102 101 222 102 201 222 110 201 222 111 101 222 111 201 222 112 101 222 112 201 222 120 201 222 121 101 222 121 201 222 122 101 222 122 201 222 202 101 222 202 201 222 210 201 222 211 101 222 211 201 222 212 101 222 212 201 222 220 201 222 221 101 222 221 201 222 222 101 222 222 202 020 202 102 020 202 202 020 211 102 020 211 202 020 212 102 020 212 202 020 221 102 020 221 202 020 222 102 020 222 202 021 021 102 021 021 202 021 022 102 021 022 202 021 102 102 021 102 202 021 111 102 021 111 202 021 112 102 021 112 202 021 121 102 021 121 202 021 122 102 021 122 202 021 202 102 021 202 202 021 211 102 021 211 202 021 212 102 021 212 202 021 221 102 021 221 202 021 222 102 021 222 202 022 021 102 022 021 202 022 022 102 022 022 202 022 102 102 022 102 202 022 111 102 022 111 202 022 112 102 022 112 202 022 121 102 022 121 202 022 122 102 022 122 202 022 202 102 022 202 202 022 211 102 022 211 202 022 212 102 022 212 202 022 221 102 022 221 202 022 222 102 022 222 202 102 102 102 202 102 111 102 102 111 202 102 112 102 102 112 202 102 121 102 102 121 202 102 122 102 102 122 202 102 202 202 102 211 102 102 211 202 102 212 102 102 212 202 102 221 102 102 221 202 102 222 102 102 222 202 110 211 102 110 211 202 110 212 102 110 212 202 110 221 102 110 221 202 110 222 102 110 222 202 111 021 202 111 022 102 111 022 202 111 102 202 111 111 102 111 111 202 111 112 102 111 112 202 111 121 102 111 121 202 111 122 102 111 122 202 111 202 202 111 211 102 111 211 202 111 212 102 111 212 202 111 221 102 111 221 202 111 222 102 111 222 202 112 021 202 112 022 102 112 022 202 112 102 202 112 111 102 112 111 202 112 112 102 112 112 202 112 121 102 112 121 202 112 122 102 112 122 202 112 202 202 112 211 102 112 211 202 112 212 102 112 212 202 112 221 102 112 221 202 112 222 102 112 222 202 120 212 102 120 212 202 120 221 102 120 221 202 120 222 102 120 222 202 121 022 102 121 022 202 121 102 202 121 111 102 121 111 202 121 112 102 121 112 202 121 121 102 121 121 202 121 122 102 121 122 202 121 202 202 121 211 102 121 211 202 121 212 102 121 212 202 121 221 102 121 221 202 121 222 102 121 222 202 122 022 102 122 022 202 122 102 202 122 111 102 122 111 202 122 112 102 122 112 202 122 121 102 122 121 202 122 122 102 122 122 202 122 202 202 122 211 102 122 211 202 122 212 102 122 212 202 122 221 102 122 221 202 122 222 102 122 222 202 202 202 211 102 202 211 202 202 212 102 202 212 202 202 221 102 202 221 202 202 222 102 202 222 202 210 221 102 210 221 202 210 222 102 210 222 202 211 022 202 211 111 102 211 111 202 211 112 102 211 112 202 211 121 102 211 121 202 211 122 102 211 122 202 211 211 102 211 211 202 211 212 102 211 212 202 211 221 102 211 221 202 211 222 102 211 222 202 212 022 202 212 111 102 212 111 202 212 112 102 212 112 202 212 121 102 212 121 202 212 122 102 212 122 202 212 211 102 212 211 202 212 212 102 212 212 202 212 221 102 212 221 202 212 222 102 212 222 202 220 222 102 220 222 202 221 111 102 221 111 202 221 112 102 221 112 202 221 121 102 221 121 202 221 122 102 221 122 202 221 211 102 221 211 202 221 212 102 221 212 202 221 221 102 221 221 202 221 222 102 221 222 202 222 111 102 222 111 202 222 112 102 222 112 202 222 121 102 222 121 202 222 122 102 222 122 202 222 211 102 222 211 202 222 212 102 222 212 202 222 221 102 222 221 202 222 222 102 222 222 211 111 111 121 111 111 221 111 112 121 111 112 221 111 121 121 111 121 221 111 122 121 111 122 221 111 211 121 111 211 221 111 212 121 111 212 221 111 221 121 111 221 221 111 222 121 111 222 221 112 111 221 112 112 121 112 112 221 112 121 121 112 121 221 112 122 121 112 122 221 112 211 221 112 212 121 112 212 221 112 221 121 112 221 221 112 222 121 112 222 221 121 121 121 221 121 122 121 121 122 221 121 211 221 121 212 121 121 212 221 121 221 221 121 222 121 121 222 221 122 112 221 122 121 221 122 122 121 122 122 221 122 212 121 122 212 221 122 221 221 122 222 121 122 222 221 212 121 221 212 122 221 212 212 221 212 221 221 212 222 221 221 221 222 221 222 122 221 222 222 222

qui donne, en décimal,

254 969 499 266 890 291 083 953 254 978 996 743 203 159 993 817 949 805 497 198 129 707 840 032 313 432 045 469 833 001 340 789 080 627 460 574 243 448 639 936 651 994 001 258 658 609 567 030 380 182 165 738 607 116 822 312 199 933 217 861 980 189 056 860 324 785 089 140 561 339 582 556 743 898 058 135 106 560 056 695 374 214 881 118 837 774 417 204 152 960 935 431 617 390 178 741 399 072 592 522 643 404 563 423 890 483 030 365 516 814 084 124 770 460 759 555 397 192 613 120 384 886 447 955 778 709 185 058 576 695 074 344 921 101 358 943 940 367 872 757 406 196 114 383 052 515 912 232 808 757 295 329 348 206 424 250 234 519 370 140 516 002 237 967 630 697 282 145 202 244 656 853 762 307 784 431 017 461 019 122 014 095 334 684 665 467 096 933 087 897 201 329 529 927 281 485 778 362 354 621 720 846 732 255 373 626 192 323 207 775 778 436 369 681 168 680 130 828 148 620 547 208 474 374 155 420 188 542 864 252 310 317 642 973 093 995 090 296 636 812 833 104 684 308 025 888 301 493 365 987 491 896 755 705 080 442 981 826 708 669 953 607 810 211 049 889 545 446 572 659 361 167 679 047 161 526 140 357 079 312 852 625 243 147 513 937 396 485 037 039 766 552 163 227 672 540 116 752 232 483 452 491 571 548 997 165 494 895 006 650 304 159 033 589 325 954 403 300 355 507 410 452 398 423 028 743 244 231 956 665 981 183 576 152 559 783 736 457 550 707 238 260 706 493 021 729 831 515 575 727 686 457 049 838 824 998 114 449 453 162 912 211 855 449 129 406 957 007 178 739 206 210 079 430 423 384 031 697 413 943 154 708 866 877 447 819 846 000 757 686 399 634 960 985 925 792 520 767 347 567 672 767 481 904 109 660 876 756 412 948 964 400 261 999 743 818 820 044 974 841 301 425 762 338 396 567 221 852 484 432 738 356 336 692 140 437 664 361 377 444 098 273 805 639 833 178 827 240 353 316 741 432 471 189 632 629 102 095 956 923 565 520 910 595 560 857 543 521 243 784 253 489 417 694 451 758 804 130 200 691 763 458 559 373 518 018 157 628 744 055 866 487 701 409 444 201 124 967 118 891 589 358 005 475 991 010 524 353 373 452 077 034 325 875 685 569 655 511 430 745 115 532 214 304 431 814 408 805 890 363 264 170 185 323 491 447 445 652 758 284 923 991 516 262 551 718 978 922 659 078 461 347 440 064 473 367 749 529 037 922 733 731 530 116 740 379 903 077 902 643 357 608 291 010 221 115 721 067 873 450 219 806 299 066 229 542 054 877 528 567 520 635 172 622 114 239 615 891 386 927 091 768 126 145 205 648 918 767 735 874 747 399 559 381 476 905 220 593 203 497 141 056 453 888 052 652 448 544 238 877 982 747 567 860 831 700 043 506 158 401 744 364 124 112 773 492 113 461 911 995 015 856 448 898 985 229 386 070 233 436 320 539 327 812 564 212 205 476 378 603 780 180 679 694 802 825 008 256 690 093 479 966 714 496 046 994 439 391 611 249 986 048 196 740 956 158 480 992 738 890 071 253 783 570 148 926 655 900 173 015 189 434 211 541 532 391 802 127 269 377 459 098 896 724 925 208 092 739 482 652 059 063 919 776 636 115 888 577 761 423 035 803 302 634 519 024 247 039 414 889 494 913 069 697 827 042 769 618 239 489 055 588 742 079 176 145 122 103 153 176 741 710 686 840 323 961 811 105 090 827 155 255 100 567 954 761 063 264 570 917 798 789 776 355 926 961 757 831 637 222 673 175 267 373 254 171 161 443 159 238 996 747 291 296 311 340 144 153 971 702 735 999 587 813 613 725 584 843 577 291 051 226 266 398 736 372 314 490 983 629 360 689 716 404 484 020 913 608 357 146 568 444 535 777 234 542 859 258 010 999 612 135 867 008 318 419 435 351 851 400 422 849 105 778 757 116 645 300 028 401 347 645 566 101 988 134 899 564 120 280 750 860 428 440 702 312 030 901 829 596 247 770 805 503 551 091 679 245 139 457 897 304 443 613 155 154 206 734 607 442 859 321 327 148 552 403 429 246 159 122 233 351 234 015 555 443 922 972 411 722 435 642 256 569 889 747 438 057 584 161 950 862 158 562 842 153 064 783 007 393 562 823 068 938 784 423 292 967 073 164 599 941 859 303 935 098 649 317 638 138 902 198 605 522 887 347 146 403 039 082 340 593 265 606 635 442 364 199 408 294 878 153 987 779 543 391 520 031 415 066 544 847 779 071 843 903 702 018 556 764 285 578 368 877 267 964 628 855 168 579 099 768 229 706 087 933 414 239 588 753 125 060 671 515 943 985 856 008 389 685 051 513 026 869 285 356 441 942 976 868 783 178 715 561 203 658 654 625 037 594 097 164 474 735 191 630 754 482 451 151 476 246 432 206 969 524 811 928 781 907 827 037 782 479 818 505 235 597 064 398 212 241 059 104 537 105 787 707 144 636 405 816 399 402 256 306 316 120 892 729 738 573 952 251 810 819 537 281 293 631 966 867 378 216 900 094 211 843 455 200 557 335 397 912 286 020 320 502 214 042 295 456 817 198 105 528 006 381 231 483 314 718 325 987 909 425 943 174 943 789 586 969 001 045 685 536 263 885 527 036 678 190 953 243 284 520 919 622 340 522 615 078 982 127 305 450 569 258 221 572 094 478 218 070 651 422 015 878 336 458 625 237 627 240 264 981 016 233 541 056 886 608 112 510 132 875 806 701 483 005 891 814 395 170 375 688 857 980 771 846 570 728 090 149 848 423 768 255 309 930 205 628 706 595 900 626 713 476 746 496 709 720 732 456 125 392 174 662 126 531 222 093 341 614 799 639 999 571 350 509 104 687 855 438 705 046 936 389 617 226 003 067 087 681 818 317 064 558 448 608 962 828 862 590 961 377 638 938 104 433 428 759 066 193 600 840 947 166 637 962 879 550 970 449 301 032 933 840 655 934 853 801 246 079 377 452 694 131 918 362 105 195 353 617 653 353 980 626 697 782 231 442 341 698 890 792 165 903 952 522 067 290 246 349 737 759 308 458 222 842 958 150 543 926 213 166 152 437 160 621 691 845 239 417 981 548 756 688 353 484 855 425 440 832 849 025 574 728 197 172 795 764 067 558 450 090 953 811 821 678 377 000 453 507 000 382 937 143 948 606 621 874 734 636 471 259 096 771 374 466 854 642 774 794 888 796 539 799 125 357 617 965 854 698 275 769 204 896 409 786 050 303 660 227 744 542 765 453 393 124 671 580 267 752 351 527 328 441 201 948 109 973 460 752 219 526 418 598 588 639 909 606 456 724 255 401 017 821 601 627 488 002 928 247 161 402 201 497 025 958 268 904 806 649 155 489 891 774 410 123 358 100 457 200 320 214 713 921 558 283 178 820 652 899 821 529 420 477 442 863 570 607 955 077 552 253 202 171 569 662 935 941 966 582 216 426 500 493 016 494 710 803 944 692 067 347 590 413 275 473 704 715 413 346 598 028 005 615 974 659 622 598 013 941 423 148 723 453 668 552 319 236 298 880 557 850 724 710 542 746 276 012 801 832 018 921 395 838 376 290 776 000 935 665 911 884 569 702 080 729 121 417 564 198 423 972 855 757 215 393 868 367 269 609 034 031 506 358 161 287 890 979 790 058 551 408 569 680 152 386 892 547 275 212 183 887 348 046 035 840 807 826 980 789 503 593 853 954 420 682 850 776 446 640 127 885 309 658 817 769 239 534 158 487 939 001 292 639 710 965 398 735 222 255 222 118 242 095 110 544 955 756 166 144 756 861 296 242 815 443 262 190 160 174 516 811 550 559 028 517 901 941 488 486 205 308 723 088 013 244 603 924 984 525 084 787 909 198 663 131 893 522 976 225 905 969 253 815 166 326 952 775 635 077 217 650 944 896 624 390 865 844 533 169 896 586 389 592 211 513 385 712 011 066 833 342 831 985 043 843 405 919 988 819 045 769 590 166 514 816 321 523 277 987 025 121 059 304 977 286 379 030 421 803 804 076 469 895 214 265 606 243 049 929 010 601 069 103 662 084 147 259 637 535 637 923 337 180 517 813 473 320 042 736 150 471 539 490 599 293 687 708 485 118 383 046 020 520 857 254 676 587 943 822 812 738 556 625 266 325 762 509 762 971 341 042 002 080 661 728 274 149 168 583 184 869 816 890 326 330 455 505 795 913 393 438 564 888 099 646 693 030 298 035 874 910 052 403 631 130 525 513 264 655 174 537 027 266 798 541 579 362 479 005 222 815 457 807 219 549 905 728 709 014 726 100 295 436 141 512 212 703 481 912 220 527 338 838 329 992 791 456 136 948 496 369 820 697 053 412 514 822 427 281 307 130 299 979 357 633 755 931 580 745 322 569 575 669 310 200 903 576 918 123 758 213 182 842 782 031 656 859 814 784 904 807 272 437 986 271 858 039 048 570 820 398 873 976 800 040 491 595 572 098 416 553 826 389 656 345 090 494 254 951 668 174 144 333 711 615 989 865 024 689 448 914 996 701 699 423 077 052 108 602 519 759 679 072 968 466 799 200 870 015 874 740 414 743 059 393 817 324 754 488 295 659 192 687 960 375 298 484 339 468 164 910 650 957 326 605 089 949 914 955 194 583 630 025 983 122 310 910 442 249 134 639 357 459 503 159 497 395 507 901 021 480 695 791 966 858 193 486 217 581 925 427 814 057 774 222 956 815 193 802 884 300 259 247 686 622 322 676 922 719 646 423 356 901 682 249 276 947 941 416 216 119 601 333 543 068 702 975 182 030 748 272 348 228 905 178 804 686 596 428 857 301 469 854 408 852 299 706 217 084 466 648 619 335 214 219 358 635 326 416 130 266 109 153 144 192 456 709 877 817 221 981 081 760 890 585 374 158 497 655 779 240 298 993 284 103 908 886 339 763 895 586 064 583 170 688 192 830 715 828 746 221 097 624 701 999 217 333 846 404 526 532 495 544 660 895 450 402 718 312 857 749 465 935 987 880 437 868 387 563 903 543 788 278 118 087 841 416 336 137 260 009 846 709 840 869 513 349 302 688 555 389 689 603 240 220 397 734 766 451 950 421 146 597 541 311 624 431 812 380 009 449 265 704 412 477 417 609 892 785 996 300 098 197 215 702 423 272 841 232 934 407 634 461 911 474 202 366 368 029 645 783 203 916 096 465 713 874 990 817 388 960 057 363 619 667 960 491 189 800 943 759 767 242 368 825 120 310 259 699 008 474 091 404 686 921 466 037 749 941 584 819 951 454 097 450 040 356 571 911 826 129 116 239 121 871 601 130 559 785 805 916 084 082 500 367 262 476 484 994 426 379 516 428 108 822 916 251 282 900 816 914 256 923 375 906 339 818 216 876 584 252 916 696 425 275 161 762 144 675 952 809 228 218 359 095 072 642 579 627 609 484 980 409 703 769 090 620 843 480 314 603 610 281 921 653 782 712 401 351 409 094 752 004 047 510 088 802 938 576 262 525 063 523 262 217 871 031 647 119 543 182 868 330 601 064 413 775 365 592 885 059 441 021 724 856 987 827 541 493 711 642 737 551 700 248 432 391 817 577 072 451 517 304 484 415 607 313 861 551 923 682 726 603 796 104 949 486 352 314 986 753 598 851 419 566 062 695 057 974 616 668 845 482 749 547 398 234 447 558 429 006 627 099 391 177 162 792 632 722 702 637 484 806 733 495 969 697 821 794 593 220 139 127 445 410 114 007 018 217 748 197 269 204 654 108 131 843 376 112 921 466 698 360 806 851 072 764 016 524 942 302 749 784 956 243 167 369 734 858 121 922 172 157 142 383 014 001 889 363 944 354 362 084 211 925 373 900 164 781 906 255 534 536 776 045 882 697 260 322 314 160 869 623 282 661 908 005 589 753 058 138 603 281 441 658 305 880 631 373 877 691 318 796 525 885 775 749 406 700 822 463 789 402 964 544 133 167 584 051 027 229 308 804 261 565 307 311 497 975 352 192 311 096 541 210 935 054 193 980 549 794 473 438 889 933 757 717 866 863 748 217 945 065 853 061 304 553 299 994 766 654 587 650 542 645 840 685 045 699 858 681 630 824 782 399 182 886 003 513 365 651 883 680 740 100 231 243 151 121 738 084 601 590 251 308 155 599 318 622 751 356 741 393 169 456 153 960 617 227 865 582 775 882 353 294 377 577 339 997 946 167 165 160 562 329 461 213 087 495 750 044 665 430 937 250 918 019 460 061 081 153 300 026 375 637 569 267 324 959 095 262 923 717 059 057 724 142 578 583 360 568 703 479 256 126 672 559 890 107 943 268 726 693 733 186 240 601 531 798 365 008 643 131 203 323 120 681 050 732 741 088 038 673 155 316 325 103 392 641 680 606 453 660 520 036 526 106 396 275 188 066 615 883 269 434 449 568 972 606 519 673 302 121 338 924 838 234 246 701 690 084 652 989 283 061 477 167 025 731 277 443 668 615 614 964 514 817 761 532 671 898 106 849 074 932 395 208 636 905 988 769 269 876 457 053 471 739 385 851 242 719 401 100 890 943 614 804 404 114 509 408 316 930 760 733 061 139 745 951 327 386 942 779 024 365 430 934 599 791 661 779 278 876 593 215 813 694 069 416 871 374 211 582 526 327 631 917 452 017 633 601 326 053 563 296 280 876 582 515 890 849 770 215 698 773 479 945 686 256 497 336 019 053 121 307 926 471 709 632 459 644 621 428 422 195 511 606 034 792 326 628 529 467 940 071 690 007 396 355 967 442 551 206 387 958 810 849 458 919 704 033 246 193 351 837 343 304 248 408 383 465 478 141 632 404 667 374 045 597 438 788 735 650 526 485 310 568 912 911 595 715 894 632 143 676 129 014 713 889 239 023 776 484 650 815 607 400 501 517 069 089 445 291 912 448 009 398 725 441 654 754 153 499 723 341 097 790 934 525 591 376 936 082 803 759 388 946 009 869 296 230 254 263 634 634 959 530 604 269 746 099 617 361 883 106 872 786 515 518 702 931 842 667 130 684 986 951 723 120 473 757 290 578 761

Une question intéressante serait de chercher si on peut coder une séquence de de Bruijn uniquement sur les positions valides.

14/12/20 à 15h34
Modifié

+3 -0

anonyme, mercredi 16 décembre 2020 à 23h20

Aabu, si tu cherchais à calculer le nombre de positions modulo les symétries, ça donne 850 ! Et c’est sans compter les positions impossibles parce qu’elles ont deux gagnants par exemple. Voilà comment on peut calculer le nombre de positions valides pour chaque couple (nombre de croix, nombre de ronds).

Déjà, le mode de représentation des nombres de possibilités utilise les polynômes en deux variables $x$ et $y$ , avec $x$ qui correspond au nombre de croix et $y$ au nombre de ronds. Par exemple, "deux possibilités pour une croix et trois possibilités pour (une croix, deux ronds)" s’exprime par le polynôme $2 x + 3 xy^2$ . Pourquoi cette représentation ?

L’addition de polynômes correspond à prendre l’union des possibilités.
Le produit de polynômes sert à faire des choix parallèles. Par exemple, si $P(x,y)$ représente les nombres de configurations possibles pour le morpion, alors $P(x,y)^2$ représentera possibilités pour deux plateaux de morpions côte à côte.

Avec cet encodage, voilà le calcul du polynôme pour le morpion, en Sage et avec le théorème de Polya.

sage: var("x,y,z")
(x, y, z)
sage: Se = (x+y+z)^9
sage: Sr = (x^4+y^4+z^4)^2*(x+y+z)
sage: Sr2 = (x^2+y^2+z^2)^4*(x+y+z)
sage: Sm = (x^2+y^2+z^2)^3*(x+y+z)^3
sage: P = (1/8) * (Se + 2*Sr + Sr2 + 4*Sm)
sage: expand(P(z=1))
x^9 + 3*x^8*y + 8*x^7*y^2 + 16*x^6*y^3 + 23*x^5*y^4 + 23*x^4*y^5 + 16*x^3*y^6 + 8*x^2*y^7 +
3*x*y^8 + y^9 + 3*x^8 + 12*x^7*y + 38*x^6*y^2 + 72*x^5*y^3 + 89*x^4*y^4 + 72*x^3*y^5 +
38*x^2*y^6 + 12*x*y^7 + 3*y^8 + 8*x^7 + 38*x^6*y + 108*x^5*y^2 + 174*x^4*y^3 + 174*x^3*y^4 +
108*x^2*y^5 + 38*x*y^6 + 8*y^7 + 16*x^6 + 72*x^5*y + 174*x^4*y^2 + 228*x^3*y^3 + 174*x^2*y^4 +
72*x*y^5 + 16*y^6 + 23*x^5 + 89*x^4*y + 174*x^3*y^2 + 174*x^2*y^3 + 89*x*y^4 + 23*y^5 + 23*x^4 +
72*x^3*y + 108*x^2*y^2 + 72*x*y^3 + 23*y^4 + 16*x^3 + 38*x^2*y + 38*x*y^2 + 16*y^3 + 8*x^2 +
12*x*y + 8*y^2 + 3*x + 3*y + 1

Chacun des polynômes $S_e$ , $S_r$ , etc. calculés correspondent à un type de symétrie du plateau de morpion : $e$ pour l’identité (la symétrie qui ne fait rien), $r$ pour une rotation d’un quart de tour (il y en a deux d’où le coefficient 2 dans le calcul de $P$ ), $r^2$ pour un demi-tour et $m$ pour une symétrie miroir (il y en a quatre). On fait ensuite la moyenne (huit symétries) et on trouve $P$ .

Le calcul des $S_e$ , $S_r$ , etc. fonctionne comme suit. On commence par dessiner l’action de la symétrie sur les cases du morpion à l’aide de flèches. Par exemple, pour la symétrie $S_r$ , on va avoir les quatre coins qui vont tourner en boucle, la case du milieu qui reste fixe et les quatre autres cases qui tournent en boucle aussi. Les deux boucles de longueurs $4$ correspondent aux deux facteurs $(x^4 + y^4 + z^4)$ dans $S_r$ et la boucle de longueur $1$ (la case qui ne bouge pas) correspond au facteur $(x+y+z)$ .

Voilà ! Maintenant vous pouvez calculer le nombre de cubes dont les faces sont coloriées avec $n$ couleurs, modulo rotations du cube, comme un polynôme en $n$ . Ce théorème a plein d’applications, notamment en chimie pour compter des nombres de molécules d’après ce qu’il se dit.

16/12/20 à 23h20

+2 -0

melepe, mardi 29 décembre 2020 à 21h42

@La Vir, gule, j’essaie de comprendre tes séries génératrices.

Se est assez simple, une case ne peut contenir que une croix, un rond ou rien. On a neuf cases donc puissance neuf.
Sr stipule que par invariance de rotation, les quatre coins sont identiques $(x^4 + y^4 + z^4)$ , on fait pareil pour les milieux (même polynôme, donc mise au carré) et enfin la case centrale est intouchée.
Sr2, chaque coin est identique à l’opposé diagonal et chaque milieu de côté est identique à son opposé. Chacun de ces termes donne un facteur $(x^2 + y^2 + z^2)$ et il y en a quatre (deux pour les coins, deux pour les côtés). Pareil, le milieu reste intouché.
Sm : dans une symétrie miroir, trois cases ne bougent pas et il n’y a donc pas de contraintes dessus (les trois cases où passe l’axe de réflexion). C’est le terme $(x + y+ z)^3$ . Le terme $(x^2 + y^2 + z^2)$ correspond aux invariances dues à la symétrie, qui affectent trois paires de cases.

Jusque-là, ça va à peu près. Par contre je ne suis pas sûr de comprendre pourquoi tu rajoutes un facteur 1/8 à P (tu as dit que c’est le nombre de transformations et j’observe que ça donne un polynôme unitaire donc j’imagine que c’est lié).

La valuation à z=1, j’ai du mal aussi. Je ne me souviens pas bien des séries génératrices à plusieurs variables, qu’est-ce que ça veut dire au final ?

Et dernière question, d’où vient le nombre de 850 ?

De mémoire, le coefficient devant un monôme indique le nombre de configurations qui mènent à cet état, ce qui veut dire qu’en retirant les symétries, il ne reste que 23 grilles de morpion complètes (5 croix et 4 ronds). Marrant.

29/12/20 à 21h42

+0 -0

anonyme, samedi 09 janvier 2021 à 22h32
Modifié

@melepe Bonsoir.

Et dernière question, d’où vient le nombre de 850 ?

Là le plus simple est de juste ajouter les coefficients de $x$ , de $xy$ , de $x^2y$ , etc. jusqu’à $x^5y^4$ . C’est le nombre total de plateaux.

La valuation à z=1, j’ai du mal aussi. Je ne me souviens pas bien des séries génératrices à plusieurs variables, qu’est-ce que ça veut dire au final ?

Dans le calcul que j’avais mis au-dessus, le $z$ compte pour une case vide mais ça facilite la lecture de supprimer le $z$ en le mettant égal à $1$ et de ne retenir que les nombres de croix et ronds (le nombre de cases vides s’en déduisant).

Par contre je ne suis pas sûr de comprendre pourquoi tu rajoutes un facteur 1/8 à P (tu as dit que c’est le nombre de transformations et j’observe que ça donne un polynôme unitaire donc j’imagine que c’est lié).

Ce moyennage vient du lemme de Burnside. Voilà un exemple : si on mélange les enfants de $n$ couples uniformément, alors en moyenne exactement un couple se retrouve avec ses enfants de départ. La raison est que chaque couple a une chance sur $n$ de se retrouver avec ses enfants de départ, et par linéarité de l’espérance ça donne une moyenne de $1 = n × 1/n$ . En généralisant on a le lemme de Burnside : si un groupe fini agit sur un ensemble fini, alors le nombre moyen de points fixes d’un élément du groupe compte le nombre d’orbites de l’action. En appliquant ça coefficient par coefficient dans les séries génératrices, on a le théorème de Polya !

Je ne sais pas si c’est très convainquant mais c’est la raison en restant un peu imprécis.

09/01/21 à 22h32
Modifié

+1 -0

melepe, samedi 09 janvier 2021 à 23h04

Très clair, merci !

09/01/21 à 23h04

+0 -0

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte