Matematyka.pl

to są ciekawe i niełatwe pytania.

Znalazłem tą sekwencję Mógłby ktoś coś napisać na ten temat? To się klei. W tym linku mamy bowiem "Number of permutations of length n within distance 2 of a fixed permutation" Czym jest odległość dwóch permutacji p i q? d(p, q) = max |p _{j} - q _{j}| : j=1,2,...,n No to czym jest nasze z...

Nie zajarzyłem, że chodzi o ilość podaną w procentach z całości:)

a co to w ogóle jest M? bo z postu nie można się tego za bardzo domyślić..

masz rację. popełniłem mały błąd logiczny w dowodzie twierdzenia, które jest zatem fałszywe.

Możliwe, że właśnie o to chodziło. Tylko w takim razie, skoro liczy się kolejność w ławkach to po co wyszczególniać, że mamy ławki 3-osobowe? Równie dobrze mogli by siedzieć na nieskończonej ławce i usiedliby (koło siebie) na tyle samo sposobów.-- 27 wrz 2011, o 22:50 --poza tym na wstępie założyłaś...

Mamy macierz n \cdot k . Jej wyrazami mogą być 0 albo 1 . Chcemy aby w i-tym wierszu suma składników była równa w _{i} a w i-tej kolumnie k _{i} . Wiemy, że \sum_{i=1}^{n}w _{i} = \sum_{i=1}^{k}k _{i} oraz dla każdego i: 1 \le w _{i} < k \wedge 1 \le k _{i} < n . Udowodnij, że jesteśmy wstanie stwor...

primo, czy ławki są rozróżnialne? (sądzę, że są)
secundo, czy może być tak, że do jednej ławki usiądzie tylko jedna albo dwie osoby?

ogólnie zadanie jest słabo sprecyzowane.

to jest ciekawe ograniczenie. -- 22 wrz 2011, o 08:58 -- Dobra, mam rozwiązanie. Zanim co, najpierw ponowię treść problemu w nieco zwięźlejszy sposób. Mamy rodzinę zero-jedynkowych macierzy n \cdot n o tej własności, że suma składników w każdym wierszu i każdej kolumnie jest \ge k . Przez moc macier...

skąd ten wzór?

zgadzam się z tą równością. być może idzie to dalej wykorzystać w dobrym kierunku. ja na razie myślę w trochę inną stronę i zobaczę, czy do czegoś mnie to doprowadzi.

no dobra ale wciąż rozważasz tylko pary: i-ty wiersz oraz i-ta kolumna. A przecież redukcja może zajść na pozycji (i,j) gdzie \(\displaystyle{ i \neq j}\).

Nieprawda właśnie. weźmy n=4, k=2. Niech w pierwszym wiersz będzie od lewej do prawej (1,1,1,0) a w czwartek kolumnie z góry na dół (0,1,1,1). I ten wiersza i ta kolumna mają nadwyżkę (\(\displaystyle{ 3>k=2}\) a mimo to nie można nic usunąć z pozycji (1,4) bo tam jest zero.

\left(\mathbf{1}^TM-k\mathbf{1}^T\right)\cdot\left(M\mathbf{1}-k\mathbf{1}\right)=0 . Mnożysz nadwyżkę jedynek w i-tym wierszu przez nadwyżkę jedynek w i-tej kolumnie macierzy M i sumujesz po i=1,...,n. Ale co ci to daje? Jeśli nawet wyjdzie wynik dodatni to o niczym to nie świadczy. Bo weźmy i-ty ...

Szczerze to nie znam się na teorii grafów bo jeszcze tego nie brałem. Jeśli k dzieli n , to chyba potrafię wskazać taki nieredukowalny układ z \frac{n(k+1)}2 jedynkami. Jeśli nie dzieli, to podobnie. Ale zauważ, że każda taka macierz ma w sumie minimum n \cdot k . Zatem sprawdźmy kiedy możesz stworz...