Vrijeme: 01:03

Diamonds & Dancefloors #2

Nakon dosadnih, običnih kvadratnih podija pozornost vam privuče jedan u obliku jednakokračnog trokuta. Naravno, kao ljubitelj matematike, odmah počinjete proučavati uzorak na njegovu podu.

Za prirodan broj n\geq 2 podij je podijeljen s n-1 dužina paralelnih s osnovicom, smještenih na jednakim razmacima po visini trokuta. Tako nastaje n+1 vodoravnih traka. Osnovica je podijeljena na n jednakih dijelova, a svaka od n-1 unutarnjih točaka spojena je s gornjim vrhom trokuta. Primjer za n=4 prikazan je na lijevoj slici.

Sva sjecišta nacrtanih dužina, uključujući točke na rubu podija i gornji vrh, označena su kao plesna mjesta. Na svako plesno mjesto može stati najviše jedna osoba.

Dvije osobe mogu se vidjeti ako njihova plesna mjesta leže na istoj nacrtanoj vodoravnoj dužini ili na istoj nacrtanoj dužini koja polazi iz gornjeg vrha. Pritom i stranice trokuta ubrajamo u nacrtane dužine, a osobe koje stoje između njih ne zaklanjaju pogled.

Na podij želimo rasporediti točno n međusobno različitih plesača tako da sa svakog praznog plesnog mjesta možemo vidjeti barem jednog plesača. Drugim riječima, svako plesno mjesto mora biti zauzeto ili ležati na istoj nacrtanoj dužini s barem jednim zauzetim mjestom. Na desnoj slici prikazan je jedan dopušten raspored za n=4.

Attachment brbrpatapim.png

Na koliko načina možemo rasporediti plesače ako je n=2026? Kao odgovor, zapiši ovaj broj modulo 2029

Plesače međusobno razlikujemo i važno nam je gdje tko stoji. Podij promatramo u fiksnom položaju: rasporede dobivene zrcaljenjem ne poistovjećujemo, osim ako svaka osoba ostane na istome mjestu.

Amidst the boring, ordinary square dance floors, one shaped like an isosceles triangle catches your eye. Naturally, as a math enthusiast, you immediately begin examining the pattern on its floor.

For a natural number n \geq 2, the floor is divided by n line segments parallel to the base, spaced evenly along the triangle's altitude. This creates n+1 horizontal strips. The base is divided into n equal parts, and each of the n-1 interior points is connected to the triangle's top vertex. An example for n=4 is shown in the image on the left.

All intersection points of the drawn segments—including points on the floor's boundary and the top vertex—are designated as *dance spots*. Each dance spot can accommodate at most one person.

Two people can see each other if their dance spots lie on the same drawn horizontal segment or on the same drawn segment originating from the top vertex. The sides of the triangle are included among the drawn segments, and people standing between them do not obstruct the view.

We wish to place exactly n distinct dancers on the floor such that at least one dancer is visible from every empty dance spot. In other words, every dance spot must either be occupied or lie on the same drawn segment as at least one occupied spot. The image on the right shows one valid arrangement for n=4.

Attachment brbrpatapim.png

In how many ways can we arrange the dancers if n=2026? As the answer, write down this number modulo 2029.

The dancers are distinguishable, and their specific positions matter. We consider the dance floor to be in a fixed position: arrangements obtained by reflection are not considered identical, unless every person remains in the same spot.