Matek segítség a világvége ellen

(1) Biztosan nem jo, mert a 24 szamod sorrendje is szamit. (pont ez a lenyeg)

--
When you tear out a man's tongue, you are not proving him a liar, you're only telling the world that you fear what he might say. -George R.R. Martin

az 1. része azért nem jó mert egy betűhöz több szám is tartozhat, az volt a feladat, hogy 1 betűhöz legalább 1 szám tartozzon, ami azt jelenti hogy 1 vagy több is lehet.

hú de rég volt már, régi szép emlékek...

mennyi az eredmény amúgy? önellenőrzésnek jól jönne.

a szorzat első része szerintem is ahogy említed, a második pedig 35!/(35-24)! <- mert egy ismétlés nélküli variációról van szó. A 35 pedig úgy jön ide hogy ennyi a maradék amit szét kell osztani.

valószínűleg nem jó mert régen tanultam már, de nagyon érdekel a megoldás!

Nagyságrendi ellenőrzés: Ha a „minden betűhöz legalább egy szám tartozzon” kitétel nem lenne ott, akkor az 59 szám mindegyikéhez egymástól függetlenül 24 betű valamelyikét rendelhetnénk, ami 24^59 ≈ 2.70e81 lehetőség. Ennél „kicsit” kisebb lesz a végeredmény, történetesen kábé a tizede. Érzésre, ha 24 betűt felírsz egy-egy cetlire, és egy játékmenet során 59 alkalommal húzol, mindig visszatéve a cetlit (tehát újra húzhatod), szerintem reális, hogy 10 játékmenetből várhatóan 1-szer fogod mind a 24-et kihúzni legalább egyszer, és 9-szer egy vagy több kimarad.

Itt egy villámgyorsan összetákolt shell szkript, amely kis értékekre egyszerűen végigveszi az összes lehetőséget, és megnézi mindegyikre, hogy jó-e. Nagyobb értékekre ne is álmodj róla hogy lefut épeszű időn belül. Viszont kisebb értékekre használható arra, hogy egy képlet helyességét leellenőrizd.

#!/bin/bash

maxszam=10
maxbetu=c

betuk="{a..$maxbetu}"
minta=""
for i in $(eval echo {1..$maxszam}); do
  minta="$minta$betuk"
done

count=0
for szo in $(eval echo $minta); do
  jo=1
  for betu in $(eval echo $betuk); do
    if [ "$szo" = "${szo#*$betu}" ]; then
      jo=0
      break
    fi
  done
  if [ $jo = 1 ]; then
    count=$((count+1))
  fi
done

echo $count

Ez pedig egy másik tákolmány szkript, amely nagy értékekre (pl. maxszam=59, maxbetu=24) is megmondja a frankót. Helyesebben a kimenetét a bc-be kell pipe-olni.

#!/bin/bash

maxszam=10
maxbetu=3

echo '
define f (x) {
  if (x <= 1) return (1);
  return (f(x-1) * x);
}
define choose (n, k) {
  return (f(n) / f(k) / f(n-k));
}
'

echo -n $maxbetu^$maxszam

k=1
while [ $k -lt $maxbetu ]; do
  if [ $((k % 2)) == 1 ]; then
    echo -n " - "
  else
    echo -n " + "
  fi

  echo -n "choose($maxbetu, $k) * ( ($maxbetu-$k)^$maxszam )"

  k=$((k+1))
done
echo

A képlet a logikai szita gondolatmenetét alkalmazza.

Ha nincs ott a kitétel, hogy mindegyik betűnek szerepelnie kell, akkor 24^59.

De sajnos így számoltuk azokat is, amelyekben csak 23 betű fordult elő. Számoljuk meg tehát, hányféleképpen lehet 23 betűhöz hozzárendelni, és korrigáljunk ennyivel. Ráadásul ne felejtsük, 24 féle képpen választhatjuk meg, hogy melyik 23 betűt engedjük és melyik 1-et nem. Tehát levonunk 24-szer 23^59-et.

De jajj! Akik csak 22 betűt tartalmaznak, azokat is az elején egyszer számoltuk, de most levontuk kétszer is, aszerint hogy melyik az a huszonharmadik betű amit elvileg engedtünk, de mégse szerepelt. Ezeket tehát megint hozzá kell adni. (24 alatt 2) féle képpen lehet kiválasztani, hogy melyik 22 betűről van szó, és 22^59 ilyen hozzárendelés van.

Na de megint túllőttünk a célon a csak 21 betűt tartalmazókkal, ezért újból le kell vonni (24 alatt 3) szor 21^59-et.

És így tovább...

Az sosem volt 100%-ig világos számomra, hogy miért mindig pont eggyel lövünk mellé minden egyes alkalommal a pont épp szóban forgó mennyiségű különböző betűt tartalmazó hozzárendelések megszámolásakor, de valahogy arról van szó, hogy ha a Pascal háromszög adott sorában a binomiális együtthatókat felváltva plusz/mínusz előjellel veszed, akkor a teljes sor összege nulla, azaz az utolsó szám előtt megállva 1. Például számoltad 1-szer, majd levontad 4-szer, majd hozzáadtad 6-szor, majd megint levontad 4-szer, akkor még hozzá kell adni 1-szer, így lesz 0. Olvass utána a logikai szitának, biztos megtalálod részletesen levezetve.

A csatolt második szkript ezt a képletet köpi ki, és kis számokra az eredménye megegyezik az első szkript által adott, simán leszámolt értékkel. Ez remélem eléggé meggyőző :)

Ha x-nek van legalább 1db nem 0 eleme - pl a k-adik koordináta: x(k), akkor az ahhoz tartozó elemekhez a mátrixban csak be kell írni az A(i,k)=y(i)/x(k) értéket. A többi érték pedig 0 és kész vagyunk. Látható, hogy nagyon sok megoldás van, nagyon alulhatározott a feladat általános esetben.

Ha pedig nincs nem 0 eleme x-nek, akkor nincs megoldás. Kivéve ha y is nullvektor, akkor minden mátrix megfelel.

2. egy "triviális" megoldás:

    y1/x1 ...   0
A =   :         :
      0   ... yn/xn

Leginkább a triviális megoldásokat kell kellő kritikával kezelni ;-)Ez kapásból nem működik, ha x-nek van 0 komponense.