Keskustelu: Yleinen keskustelu: Kombinatorinen ohjelmointitehtävä

Oletetaan, että 6 x 4 -taulukon sarakesummat ovat
22, 24, 39, 61, 73, 81 ja että rivisummat ovat
54, 70, 78, 98. Kuinka monella tavalla kokonaisluvut
1, 2, ..., 24 voidaan sijoittaa taulukkoon siten,
että kutakin lukua käytetään täsmälleen yhden kerran?

Oikein vastanneelle luvassa 100 euroa:
http://www.survo.fi/ristikot/index.html#170907

Jos tehtävä tuntuu helpolta, niin lisähaastetta
löytyy osoitteesta:
http://www.survo.fi/cgi/board/board.cgi?&read­=001178-000000.msg&area=keskustelua_survosta

Reijo kirjoitti:

Oikein vastanneelle luvassa 100 euroa:
http://www.survo.fi/ristikot/index.html#170907

Tuossahan sanotaan selvästi, että oikein vastanneiden kesken arvotaan 100 euron palkinto, eli kaikki eivät saa satasta.

Aihe on kiinnostava, toivottavasti moni innostuu laatimaan ohjelmia.

Tuo lisätehtävä vaikuttaa todella haastavalta. Onkohan luvun S(5,5) suuruudesta mitään arviota?

Antti Laaksonen kirjoitti:

Onkohan luvun S(5,5) suuruudesta mitään arviota?

Luku S(5,5) on hankala tapaus. Sopivilla epäyhtälöehdoilla olisi
teoriassa mahdollista arvioida ainakin yksikäsitteisesti ratkeavien
tapausten yläraja, mutta käytännössä sekin lienee varsin työlästä.

Karkeaa arvausta voi yrittää mallintamalla ja ekstrapoloimalla
lisätehtävässä esitetyn taulukon lukuja. Hyvän mallin löytäminen onkin
sitten ihan eri juttu. Näyttäisi kuitenkin siltä, että luvun S(5,5)
suuruusluokka on miljoonia - ehkä jopa kymmeniä miljoonia.

Suuruudesta ei tietääkseni ole esitetty tämän kummempaa arviota. Ehkä onnistuisitte työstämään paremman?

Osoitteessa http://www.uta.fi/laitokset/mattiet/uutinen.php?item=15942 arvioidaan S(5,5):n olevan miljoonia, mutta ei kymmeniä miljoonia. Luulisin, että Monte Carlo -simulaatiolla voisi saada jonkun arvion erilaisten Survojen määrälle.