Un défi par semaine

Septembre 2020, 4e défi

Le 25 septembre 2020  - Ecrit par  Ana Rechtman Voir les commentaires (16)
Lire l'article en  

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante. Le calendrier 2020 est en vente !

Semaine 39 On cherche à recouvrir complètement un carré de $23 \times 23$ cm par des carrés de $1\times 1$, $2 \times 2$ et $3 \times 3$ cm. Quel est le nombre minimal de carrés de $1\times 1$ cm qu’il faut utiliser ?

Solution du 3e défi de septembre :

Enoncé

La réponse est : $13$ nombres.

Analysons toutes les valeurs possibles pour $a$.

  • Si $a=1$ et $n$ est parent de $ab$, alors la seule possibilité est $n=1b$ ($1b$ divise évidemment $1b$).
  • Si $a=2$, les seuls parents possibles de $2b$ sont $11b$ et $2b$ mais il faut que $2b$ soit leur diviseur.

Si un nombre est diviseur de deux nombres, il est aussi diviseur de leur différence. Ici la différence entre $2b$ et $11b$ est $90$, $2b$ doit donc être un diviseur de $90$.

Il n’existe cependant pas de diviseur de $90$ qui soit de la forme $20+b$, il n’y a donc pas de nombres parents dans ce cas.

  • Si $a \geq 3$, puisque $ab$ doit diviser $(a-3)21b$ et $(a-3)12b$, il doit également diviser leur différence, qui est $1000(a-3)+200+10+b-1000(a-3)-100-20-b=90$.

Les seules possibilités pour $ab$ sont donc $30$, $45$ et $90$ puisque $ab\geq 30$.

Vérifions maintenant si $30$, $45$ et $90$ divisent tous leurs parents.

Si $n$ est parent de $30$ alors $n=A0$ où $A$ est un nombre entier dont la somme des chiffres est $3$.

Le nombre $n$ est donc multiple de $10$ et de $3$ et donc de $30$ aussi.

Si $n$ est parent de $45$ alors $n=A5$ où $A$ est un
nombre dont la somme des chiffres est $4$. La somme des chiffres de $n$ est donc $9$, ce qui implique qu’il est multiple de $9$.

Ce nombre $n$ est également multiple de $5$ puisqu’il finit par le chiffre $5$, c’est donc un multiple de $45$.

Si $n$ est parent de $90$ alors $n=A0$ où $A$ est un nombre entier dont la somme des chiffres est $9$.

Il est multiple de $9$ et de $10$, il est donc aussi multiple de $90$.

Ainsi, les seuls entiers à deux chiffres qui divisent tous leurs parents sont :
$10$, $11$, $12$, $13$, $14$, $15$, $16$, $17$, $18$, $19$, $30$, $45$ et $90$, il en existe $13$.

Post-scriptum :

Calendrier mathématique 2020 - Sous la direction d’Ana Rechtman, avec la contribution de Nicolas Hussenot - Textes : Serge Abiteboul, Charlotte Truchet. 2019, Presses universitaires de Grenoble. Tous droits réservés.

Disponible en librairie et sur www.pug.fr

Partager cet article

Pour citer cet article :

Ana Rechtman — «Septembre 2020, 4e défi» — Images des Mathématiques, CNRS, 2020

Crédits image :

Image à la une - EQROY / SHUTTERSTOCK

Commentaire sur l'article

  • Septembre 2020, 4e défi

    le 25 septembre à 11:57, par jokemath

    Je pense que l’on peut n’utiliser que 2 carrés de 1x1.

    Répondre à ce message
  • Septembre 2020, 4e défi

    le 25 septembre à 12:02, par jokemath

    Erreur, je voulais dire 4 carrés de 1x1.

    En fait, 102 carrés de 2x2, 13 carrés de 3x3 et 4 carrés de 1x1.
    En aire, cela donne
    102×4+13×9+4×1=529, soit 23×23.

    Répondre à ce message
    • Septembre 2020, 4e défi

      le 25 septembre à 13:21, par François

      J’ai aussi 49 carrés 3*3 et 21 carrés 2*2, restent 4 carrés 1*1.
      Mais est-ce le minimum ?

      Répondre à ce message
  • Septembre 2020, 4e défi

    le 25 septembre à 19:10, par Niak

    Il est possible de n’utiliser qu’un seul bloc $1\times1$ (voir par exemple l’image jointe).

    On ne peut pas faire mieux. Pour le voir, colorions les diagonales du carré quadrillé $23\times23$ avec $3$ couleurs $\{0,1,2\}$ dans l’ordre de façon cyclique, i.e. la case $(i,j)$ reçoit la couleur $(i+j)\bmod3$. Avec ce coloriage, on obtient $176$ cases de couleur $0$, $177$ cases $1$ et $176$ cases $2$. Placer un bloc $3\times3$ n’importe où couvre exactement $3$ cases de chaque couleur. Placer un bloc $2\times2$ couvre exactement $2$ cases de $2$ couleurs qui dépendent de la position.

    Couvrir le carré sans bloc $1\times1$ implique que l’on peut atteindre le vecteur $[176,177,176]$ avec une combinaison linéaire des vecteurs $[3,3,3]$, $[0,2,2]$, $[2,0,2]$ et $[2,2,0]$. Il est flagrant que c’est impossible en regardant ces vecteurs modulo $2$.

    Document joint : cov.png
    Répondre à ce message
    • Septembre 2020, 4e défi

      le 25 septembre à 19:37, par olivier

      Très joli !

      Répondre à ce message
      • Septembre 2020, 4e défi

        le 25 septembre à 20:10, par Niak

        Merci.

        Petite précision, quand je parle de combinaison linéaire, il faut bien sûr comprendre à coefficients entiers (et même positifs, mais ça importe peu en l’occurrence) dans ce contexte.

        Et pour compléter, puisque ça n’a pas été trouvé non plus, voici des solutions à $2$ et $3$ blocs $1\times1$.

        Document joint : cov23.png
        Répondre à ce message
    • Septembre 2020, 4e défi

      le 26 septembre à 12:22, par François

      J’ai pas tout compris à votre démonstration :
      En coloriant par $(i,j) \to i+j$ mod $3$ , un carré $2$x$2$ donne :
      $i + j$ , $i+j+1$
      $i+j+1$, $i+j+2$
      Soit $(1,2,1)$ ou $(1,1,2)$ ou $(2,1,1)$ suivant que $i+j = 0 ,1, 2 $ mod $3$
      Le système
      $3k_1+ k_2+k_3+2k_4 =176$
      $3k_1+2k_2+k_3+k_4=177$
      $3k_1+k_2+2k_3+k_4 = 176$
      admet pour solutions $k_1=57-4p$, $k_2=2+3p$, $k_3=1+3p$, $k_4=1+3p$ avec $0\leq p \leq 14$
      On retrouve les valeurs d’Olivier, mais cela ne prouve pas que 0 carré $1$x$1$ est impossible (ce qui est vraisemblable)
      A moins que j’ai tout faux !

      Répondre à ce message
      • Septembre 2020, 4e défi

        le 26 septembre à 13:02, par Niak

        Arg, houlà, oui oui, je me suis embrouillé en griffonnant un peu trop vite ma preuve dans la tête...

        Cela dit, mon argument fonctionne en coloriant par exemple plutôt les lignes, i.e. $(i,j)\mapsto i\bmod3$. Dans ce cas on cherche à atteindre le vecteur $[184, 184, 161]$ avec les mêmes vecteurs que ceux donnés dans mon premier message, et c’est tout aussi clairement impossible pour les mêmes raisons de parité.

        Merci pour votre relecture attentive !

        Répondre à ce message
      • Septembre 2020, 4e défi

        le 26 septembre à 13:48, par Niak

        Une petite remarque au passage. L’argument précédent consiste à colorier les lignes ${}\bmod 3$ puis regarder le résultat $\bmod 2$. Mais il est parfaitement valable (de façon « duale » en quelque sorte) de colorier les lignes ${}\bmod 2$ : on cherche alors à atteindre le vecteur $[276, 253]$ avec les vecteurs $[6,3]$ ou $[3,6]$ pour les blocs $3\times3$ et le vecteur $[2,2]$ pour les blocs $2\times2$, ce qui est clairement impossible en regardant cette fois ces vecteurs ${}\bmod3$.

        Répondre à ce message
        • Septembre 2020, 4e défi

          le 26 septembre à 16:39, par François

          Tout à fait d’accord. Cela entraine-t-il une généralisation ?

          Répondre à ce message
          • Septembre 2020, 4e défi

            le 26 septembre à 18:13, par Niak

            Je ne sais pas. Vous pensez à quel genre de généralisation ?

            Répondre à ce message
            • Septembre 2020, 4e défi

              le 26 septembre à 19:33, par François

              Par exemple des carrés $n$x$n$ à recouvrir avec des carrés $p$x$p$ et $q$x$q$ avec $n$ premier et $p$ et $q$ premiers entre eux. Mais je ne me lancerai pas dans cette direction. En lien avec les semi-groupes ?

              Répondre à ce message
  • Septembre 2020, 4e défi

    le 25 septembre à 19:29, par olivier

    Bonjour
    Voici les 15 sommes de carrés de 2 et de 3 qui fournissent 23² (=529)
    23² = 130 . 2² + 1 . 3²
    23² = 121 . 2² + 5 . 3²
    23² = 112 . 2² + 9 . 3²
    23² = 103 . 2² + 13 . 3²
    23² = 94 . 2² + 17 . 3²
    23² = 85 . 2² + 21 . 3²
    23² = 76 . 2² + 25 . 3²
    23² = 67 . 2² + 29 . 3²
    23² = 58 . 2² + 33 . 3²
    23² = 49 . 2² + 37 . 3²
    23² = 40 . 2² + 41 . 3²
    23² = 31 . 2² + 45 . 3²
    23² = 22 . 2² + 49 . 3²
    23² = 13 . 2² + 53 . 3²
    23² = 4 . 2² + 57 . 3²
    Faire une couverture sans carré de 1x1 est donc envisageable. Reste à voir si ca s’emboîte bien...

    Il y a 14 sommes qui fournissent 528 et 14 également qui fournissent 527

    Quant à un pavage avec 4 carrés de 1x1, il existe et se trouve rapidement (pièce jointe)
    S’il y a mieux c’est donc avec l’une des 15 + 14 + 14 combinaisons précédentes.

    Document joint : image-3.png
    Répondre à ce message
    • Septembre 2020, 4e défi

      le 30 septembre à 11:06, par PGBriis

      bonjour,
      dans l’enonce, je lis :« On cherche à recouvrir complètement un carré de 23×23 cm par des carrés de 1×1, 2×2 et 3×3 cm. »
      donc je comprends que l’on recherche les coefficients m, n et p non nuls correspondants aux trois carrés tels que m*1X1+n*2X2+p*3X3=531.
      De plus, m doit etre minimum.
      pour moi, une reponse est m=1, n=2 et p=58 : 1X1+2*2X2+58*3X3=531

      une reponse est donc : il faut minimum 1 carré de 1X1.

      bonne journée.

      Répondre à ce message
  • Septembre 2020, 4e défi

    le 11 octobre à 14:26, par Christophe Boilley

    Pour montrer qu’il est impossible de remplir le carré avec seulement des carrés 3×3 et des carrés 2×2, on peut aussi remarquer que sur chaque ligne, le nombre de cases dans des carrés 2×2 est pair. Donc le nombre de carrés 3×3 qui commencent sur la 1re ligne est impair. Par conséquent, le nombre de carrés 3×3 qui commencent sur la 2e ligne est pair, et idem sur la 3e. Et ainsi de suite, le nombre de carrés 3×3 qui commencent sur la k-ième ligne est impair si et seulement si k≡1 [3], ce qui est absurde car on ne peut faire commencer un carré 3×3 sur l’avant-dernière ligne (k=22).

    Plus généralement, si on veut remplir un carré n×n avec des carrés p×p et des carrés q×q, avec 1<p<q, on se restreint au cas où p et q sont premiers entre eux (sinon on divise n, p, et q par pgcd(p,q)). On note alors n=pu+qv.
    Le nombre de carrés p×p commençant sur la 1re ligne est congru à u modulo q, comme sur toute ligne congrue à 1 modulo p. Donc n doit être un multiple de p.

    Réciproquement, si p divise n alors le carré n×n est pavable par des carrés p×p uniquement.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?