Malbonaj najbaroj
LA DEFIO
Ekzistas grupo da homoj, kiuj ne povas loĝi apud unu la alian en domoj laŭlonge de strato. Se estas 10 domoj, laŭ kiom da manieroj iuj el ĉi tiuj homoj povas loĝi en ĉi tiuj domoj tiel, ke neniuj du najbaraj domoj havas ĉi tiujn homojn en si? Kalkulu, ke ĉiuj domoj estas malplenaj, kiel unu el la eblecoj.

ESPLORADO
Kiom da manieroj estas se estas 15 domoj? Trovu ŝablonon, kiu helpos vin rapide kalkuli kiom da malsamaj manieroj por pli granda nombro da domoj.
Notoj
LA DEFIO KAJ ESPLORADO
Kiel ĉe tiom da enigmoj, la plej bona maniero lerni pri tio estas per simplaj ekzemploj serĉante ŝablonojn. Uzu E por malplena kaj B por malbona najbaro.
- 1 domo – 2 vojoj: E aŭ B
- 2 domoj – 3 vojoj: EE, BE, EB
- 3 domoj – 5 vojoj: EEE, BEE, EBE, EEB, BEB
- 4 domoj - 8 manieroj: EEEE, BEEE, EBEE, EEBE, EEEB, BEBE, BEEB, EBEB
Ŝajnas, ke ili estas la nombroj de Fibonaĉi. Ni trovu bonan kialon, kial tio devus esti.
Por trovi la nombron da manieroj plenigi n domojn, komencu per aŭ E aŭ B.
- Se vi komencas per E, tiam la sekvaj n-1 domoj povas esti plenigitaj ignorante tiun unuan domon.
- Se vi komencas per B, tiam la sekva domo devas esti E. Post tiuj du, la sekvaj n-2 domoj povas esti plenigitaj ignorante la unuajn du domojn.
Tial, la nombro da manieroj plenigi n domojn egalas al la nombro da manieroj plenigi n-1 domojn plus la nombro da manieroj plenigi n-2 domojn. Ĉi tio estas ĝuste la regulo por kalkuli la nombrojn de Fibonaĉi. Ĉar ni komencas kun 2 kaj 3, la regulo devigos la ceterajn nombrojn esti la samaj post tio.
La nombroj estos: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 por la unuaj dek.