Koľko existuje nula-jednotkových matíc rozmeru n × n, ktoré majú v každom riadku aj v každom stĺpci maximálne dve jednotky?
Timothy sa neunúva dať na túto otázku odpoveď (zrejme je to pre neho príliš triviálne), ale normálnych smrteľníkov ako my môže takáto úloha celkom potrápiť. Priznám sa, že som nad ňou uvažoval skoro pol hodiny a nepodarilo sa mi odvodiť všeobecný vzorček; niekedy to človeku skrátka nezapne. Ale Vy budete možno úspešnejší...
5 komentárov:
Len prva myslienka (mozna to bude pre vacsinu zrejme :) ):
1. zda sa mi ze by z kazdeho mozneho riesenia sa da vytvorit lubovolne riesenie (riesenie = matica splnajuca podmienky) sposobom zameny riadkov a stlpcov
2. Kazda zamena stlpca alebo riadku z matice splnajucej riesenie dostavame riesenie
To by znamenalo zobrat jedno riesenie a spocitat pocet moznych zamen - ale predpokladam, ze tam nastanu duplicity ...
Rori: Takéto úvahy ohľadom permutácie riadkov a stĺpcov sú v princípe rozumné a možno pomôžu, ale nebude to až také jednoduché.
Totiž napríklad nie je pravda, že akékoľvek riešenie (v Tvojej terminológii) je možné získať z akéhokoľvek iného riešenia len zámenou riadkov a stĺpcov; napríklad matica so samými nulami je riešením, ale akékoľvek prehodenie riadkov a stĺpcov dá opäť len nulovú maticu. Navyše niektoré riešenia sú také, že sa zmenia akoukoľvek permutáciou riadkov alebo stĺpcov (napríklad matica, ktorá má všade nuly, len na diagonále jednotky je taká), zatiaľčo iné sú invariantné vzhľadom k niektorým permutáciám a vzhľadom k iným permutáciám nie (napríklad taká matica, ktorá má samé nuly, okrem štyroch jednotiek v ľavom hornom rohu 2x2).
Zatiaľ sa nikto neozval, čiže možno to nie je až také triviálne. O to viac by ma to riešenie zaujímalo.
Nič pekné mi tam nevychádza, a tá výsledná postupnosť nemá žiaden rozumný výskyt na Googli, takže triviálny uzavretý tvar to mať asi nebude :)
Ale dá sa to rátať v polynomiálnom čase: označ si P(r,s1,s2) počet obdĺžnikových matíc, ktoré majú r riadkov a s1+s2 stĺpcov, pričom každý z prvých s1 stĺpcov má najviac jednu a každý zo zvyšných s2 stĺpcov najviac dve jednotky. Potom hľadáme hodnoty P(n,0,n), a každú hodnotu P(r,s1,s2) vieme vyjadriť pomocou max. piatich hodnôt P(r-1,?,?).
Toto je prvých 10 členov, ak som sa nesekol: 2, 16, 265, 7343, 304186, 17525812, 1336221251, 129980132305, 15686404067098, 2297230134084416.
misof: Hm. Asi ten výsledok teda naozaj nie je možné pekne zapísať. Trochu som z toho sklamaný; zdá sa mi to ako taký malý podfuk. Podľa mňa mohol Gowers čakať, že odhodlaný čitateľ sa bude snažiť tie jeho príklady rôznych typov matematických tvrdení aj vyriešiť a toto skôr vedie k frustrácii a nie k potešeniu z riešenia. Skôr je to možno práve príklad pre informatikov s cieľom nájsť asymptoticky rýchlejší ako triviálny (exponenciálny) algoritmus výpočtu tých čísel.
Inak ten Tvoj spôsob polynomiálneho výpočtu sa zdá byť OK. A asi aj tie čísla sedia, minimálne prvé tri sú určite dobre :-)
Az pridete na spravne riesenie a vzajomne si ho overite, mozete to dat s adekvatnymi odkazmi do OEIS - zatial tam nic take nie je.
Zverejnenie komentára