Staffetta combinatoria.

[Sonner]

ho poche idee anche io
proviamo con questo:

si ricopre una scacchiera 8x8 con piastrelle 3x1. resta una casella vuota.
dove può trovarsi?

Coloro la scacchiera di tre colori diversi secondo le diagonali.
La prima volta inizio a colorare da a8 fino ad h1 (quindi, ad esempio, a8 sarà di un colore A, a7-b8 di un altro colore B, a6-b7-c8 di un altro colore ancora C). In questo modo ottengo 21 A, 22 B e 21 C. Ogni tassello ricopre necessariamente una casella A, una B e una C: la scacchiera per essere riempita deve quindi essere privata di una casella B (così le caselle sarebbero 21 per tipo).
Ora posso colorare una seconda volta la scacchiera ma partendo dal vertice in alto a destra (h8) e secondo diagonali perpendicolari alle precedenti. Anche qui, le caselle B sono 22, quindi dovrò eliminare una di loro. E' ovvio quindi che posso eliminare solo quelle caselle che sono colorate del colore B in entrambi i casi. Le caselle che soddisfano ciò sono solo 4: c3, c6, f3, f6. Non mi resta che provare che esiste una tassellazione della scacchiera eliminando una di queste caselle.

Nell'allegato mostro una tassellazione che funziona per la casella c3 (notare i fantastici disegnini ). Questo basta a dimostrare che esiste una tassellazione per tutte e 4 le caselle scelte precedentemente (è sufficiente ruotare la scacchiera).

Sono passato da incomprensibile a prolisso, vabbè :S

[Spammowarrior]

il ragionamento è quello giusto, sulla comprensibilità non mi esprimo: l'ho capito ma sapevo già la soluzione

a te il prossimo, se vuoi però magari scrivi meglio la soluzione di questo

[dario2994]

Ma soprattutto... almeno sprecati a dire che esiste un esempio (più o meno banale che sia) di tasselazione che soddisfa i tuoi buchi

[Spammowarrior]

Ma soprattutto... almeno sprecati a dire che esiste un esempio (più o meno banale che sia) di tasselazione che soddisfa i tuoi buchi

uhm, che nabbo che sono

sì, ovviamente la dimostrazione non è completa, sarebbe il caso di fare una tabella o un disegno per mostrare che quei posti vanno bene
appena lo fai vai pure con il prossimo.

[Sonner]

Ho modificato, spero si capisca di più.... in ogni caso vi posto il prossimo

In una griglia AxB inserisco in ogni casella +1 o -1, in quanti modi posso farlo sapendo che il prodotto dei numeri di ogni riga e ogni colonna è -1?

[dario2994]

Allora... prima di tutto sostituisco 1,-1 con 0,1 e faccio diventare l'ipotesi che le somme siano dispari (ci sono a colonne e b righe) .
Allora:
Chiamo $ $k_{i,j} $ l'elemento sulla j-esima riga e la i-esima colonna. Chiamo $ $C_i $ la somma degli elementi sulla i-esima colonna tranne l'ultimo e $ $R_j $ la somma degli elementi sulla j-esima riga tranne l'ultimo ed S la somma totale.
Caso1 : a,b hanno parità differente, allora non esiste una disposizione che rispetti le richieste.
Assumo esista... valgono le seguenti congruenze ottenute calcolando S come somma delle righe o come somma delle colonne, sfruttando la loro disparità:
$ $S\equiv b \pmod{2} $
$ $S\equiv a\pmod{2} $
Quindi deve valere $ $a\equiv b\pmod{2} $ assurdo.

Caso 2: a,b hanno la stessa parità allora esistono $ $2^{(a-1)(b-1)} $ modi.
Metto i numeri a caso nella "sottogriglia" a-1xb-1 ottenuta dalla precedente togliendo l'ultima riga e colonna. Ho $ $2^{(a-1)(b-1)} $ modi diversi per farlo. Mostro che il resto è determinato ed esistente.
Deve valere perchè siano rispettate le ipotesi $ $k_{a,j}\equiv R_j+1\pmod{2} $ e $ $k_i,b\equiv C_i+1\pmod{2} $ (da queste ricavo che sono definiti tutti gli elementi tranne quello all'angolo) sommo le congruenze al variare di i,j ottenendo:
$ $C_a\equiv b-1+\sum_j^{b-1}R_j\equiv a-1+\sum_i^{a-1}C_i\equiv R_b\pmod{2} $
Da cui vale $ $C_a\equiv C_b\pmod{2} $ e quindi la parità del numero nell'angolo è ben definita (diversa da quelle 2) ed è unica.

p.s. forse non è mucho chiara xD

[dario2994]

Posto il nuovo problema, in caso la soluzione del precedente fosse sbagliata ditelo.

Problema 10 (Balkan 1994 problema 4)
Trovare il più piccolo $ $n\ge 5 $ per cui esiste un gruppo di $ $n $ persone tale che 2 persone che si conoscono non hanno conoscenze comuni e 2 persone che non si conoscono hanno esattamente 2 conoscenze comuni.

[Anér]

Dimostriamo prima che con meno di 16 persone non si può, poi che con 16 si può.

Innanzitutto dimostriamo che se ci sono più di 4 persone ma meno di 16, allora ce ne sono 7 oppure 11. Sia Alberto una persona, supponiamo che conosca altre k persone che formano un insieme A, e sia B l'insieme delle persone che Alberto non conosce. Allora
1) Ogni persona di B conosce esattamente due tra le k persone di A perché non conosce Alberto;
2) Ogni coppia di persone appartenenti ad A non si conosce perché conosce Alberto, quindi ha due conoscenze in comune; una è Alberto, l'altra deve essere una persona in B

Dunque esistono tante coppie non ordinate in A quante persone in B, ossia in tutto le n persone sono $ 1+k+\binom{k}{2} $, e questo, oltre a limitare a 7 e 11 la scelta di n (valori che si ottengono per k uguale a 3 e 4), ci dice che tutte le persone hanno lo stesso numero di conoscenze, in quanto Alberto per ipotesi è una persona qualunque.
Con 7 persone ve ne sono 3 in A e 3 in B (sempre supponendo di aver fissato Alberto); Alberto conosce già 3 persone, ma anche ognuna delle persone in A conosce 3 persone (Alberto più due persone in B, una per ogni coppia di A di cui fa parte); dunque Alberto ed A hanno concluso le loro conoscenze, perciò gli elementi di B, che per ora sono a due conoscenze, devono trovare sempre in B la terza, tuttavia formerebbero un triangolo con gli elementi di A.
Con 11 persone ci sono 4 persone in A e 6 in B. Di nuovo Alberto e A hanno già concluso le loro conoscenze, dunque le 6 persone in B devono trovare da sole le altre 2 conoscenze che mancano loro. Tuttavia se Barbara e Cristina sono in B, si possono conoscere solo se non hanno conoscenze comuni in A, e poiché in A ci sono 4 persone, i 2 conoscenti di Barbara devono essere i 2 non conoscenti di Cristina e viceversa. Allora ogni persona in B ha una sola persona da conoscere in B, ma ha bisogno di 2 conoscenze.

Se invece abbiamo 16 persone (k=5), allora associamo ad ogni persona un vettore $ (a,b,c,d)\in \{ 0,1\}^4 $ e imponiamo che due persone si conoscano se e solo se i loro vettori differiscono o per una componente o per tutte le componenti. Qui chiederei a chi se ne intende di correzione di problemi olimpici se sia anche necessario spiegare perché l'esempio funzioni o basti indicarlo.

Problema 11. In una galassia molto lontana c'è un pianeta molto lontano e abitato da una civiltà sviluppata. Il pianeta è diviso in stati che vanno tutti d'accordo tra loro e hanno formato una sorta di ONU per scopi civili ed economici. L'acqua è presente solo in laghi interni agli stati, mancano oceani. Il presidente dell'ONU deve svolgere due importanti lavori:
1) Dotare il pianeta di una linea ferroviaria che percorra tutti i confini degli stati del pianeta tornando al punto di partenza e senza passare due volte per lo stesso tratto (ma con la possibilità di incrociare il proprio tragitto).
2) Selezionare un membro per ogni stato per una esplorazione interplanetaria, ed affidare a ciascuno di essi il compito di ingegnere o pilota sull'astronave, in modo che membri di stati confinanti svolgano mansioni diverse.
Sapendo che può svolgere uno dei due lavori, dimostrare che può svolgere anche l'altro.

N.B.: gli stati sono connessi, ossia si può viaggiare da un punto a un altro dello stato senza passare per un altro stato.

Questo problema, privato della cornice fantascientifica, è quello che devono aver risolto gli sviluppatori di Paint, ma anche di altri programmi di grafica, perché si potesse esser certi che lo strumento "Selezione parte" funzionasse, ed è stato proprio Paint a ispirarmelo.

[Jessica92]

Beh allora dobbiamo dire anche che su questo pianeta nessuno stato ha un territorio tale da dividere la superficie in zone non connesse.

Avrebbè sennò troppa influenza su altri stati

[Anér]

La stessa critica mi è arrivata da Jessica92 e da abc per messaggio privato. Effettivamente ho dimenticato l'ipotesi che ci si possa spostare da un punto all'altro dei confini degli stati camminando solo sui confini stessi. Specifico inoltre, su richiesta di abc, che il treno deve percorrere tutti i confini di tutti gli stati, e che deve poi tornare al punto di partenza, senza mai percorrere due volte lo stesso tratto, ma con la possibilità di passare più volte per singoli punti.

[Anér]

Visto che sono passati quasi sette mesi e nessuno ha risposto, e visto che l'oliforum ha riaperto da poco e va riavviata anche la staffetta di combinatoria, metto una soluzione di questo problema e ne propongo un altro.

Intanto introduciamo un bel grafo, che ha come vertici i punti dei confini in cui si incontrano almeno 3 nazioni e come archi i tratti di confine che collegano due vertici e dividono due nazioni confinanti. Chiaramente il problema è banale se ci sono solo 2 nazioni che confinano lungo una linea semplice chiusa, per cui supponiamo che il grafo sia "consistente". Questo grafo è planare, e inoltre ogni regione non confina con se stessa (credo che nessuno abbia dubbi sul fatto che uno stato non può confinare con se stesso), e camminando sui confini si può passare da un punto a un altro qualsiasi, ossia è un grafo connesso. Possiamo poi definire il multigrafo duale di questo grafo (multigrafo= grafo in cui 2 vertici possono avere tanti archi che li collegano, mi pare si dica così), piazzando un vertice nuovo in ogni regione e collegando due vertici (regioni) se confinano con un arco del vecchio grafo; in questo modo si ottiene un multigrafo sempre planare in cui quelli che erano vertici sono divenuti regioni e viceversa, mentre gli archi sono rimasti archi. Chiamiamo G il primo grafo e H il secondo (il multigrafo duale del primo).
Supponiamo ora che si possano scegliere piloti e ingegneri in modo da rispettare la regola. Allora se prendiamo un qualsiasi vertice di G e guardiamo le regioni che confluiscono in esso, notiamo che esse si dispongono intorno a G alternativamente nei due tipi (pilota e ingegnere), dunque sono in numero pari, dunque anche i confini che separano tali facce di un vertice sono in numero pari, ossia ogni vertice di G ha grado pari. Per un noto teorema di Eulero, dato che G è connesso, esiste un ciclo euleriano che passa per tutti gli archi e torna al punto di partenza, e la linea ferroviaria percorrerà un siffatto ciclo.
Se invece si può fare la linea ferroviaria allora G ammette un ciclo euleriano, dunque ha tutti i vertici di grado pari. Passando al duale H si ha che in quest'ultimo multigrafo tutte le regioni sono delimitate da un numero pari di archi. Allora se prendiamo un ciclo (percorso chiuso che non si autointerseca) in questo grafo esso ha lunghezza pari, in quanto ogni ciclo racchiude un po' di regioni, e per fare il conto degli archi del ciclo sommiamo i perimetri delle singole regioni e poi togliamo 2 volte gli archi interni al ciclo, quelli che separano due facce interne del ciclo, dunque otteniamo un numero pari. Allora H ha tutti cicli pari ed è bipartito, e dato che i vertici di H non sono altro che le regioni di G, si ha che anche le regioni di G sono bipartite in due classi tali che due regioni della stessa classe non confinano, e basterà scegliere piloti in una classe e ingegneri nell'altra.

Problema 12.
Dato $ n\geq 2,\quad n\in\mathbb{N} $ dimostrare che ogni grafo su $ n $ vertici contiene almeno una coppia di vertici con lo stesso grado, e che effettivamente esiste un grafo (su $ n $ vertici) con una sola coppia di vertici con lo stesso grado.

[dario2994]

Allora:
Considero un grafo con n vertici ì, allora i possibili gradi sono $\{0,1,\dots n-1\}$ ma chiaramente non può esistere sia un vertice di grado 0 sia uno di grado n-1 quindi in realtà sono presenti al massimo n-1 gradi diversi -> 2 vertici hanno lo stesso grado per pidgeon hole
Esiste un n-grafo con 2 soli vertici dello stesso grado e lo costruisco in maniera induttiva:
Parto dal 2-grafo "segmento", poi aggiungo un vertice e non lo collego a nulla (3-grafo), poi aggiungo un vertice e lo collego a tutto (4-grafo). Continuo a fare così e si dimostra in un attimo che funziona
Appena me ne viene in mente uno propongo il nuovo problema di combinatoria

[dario2994]

Problema 13
Per ogni intero $n\ge 2$ sia $N(n)$ il massimo numero di triple $(a_i,b_i,c_i)\ con\ i=1,2,\dots ,N(n)$ di interi non negativi tali che valgono:

• $\forall\ 1\le i\le N(n)\ \ a_i+b_i+c_i=n$
• $i\not=j\Rightarrow\ a_i\not=a_j\wedge\ b_i\not=b_j\wedge\ c_i\not=c_j$

Determinare $N(n)$ per ogni $n\ge 2$

[paga92aren]

Possono esistere al massimo $n+1$ $a_i$. Altrimenti o avremmo due $a_i$ uguali o un $a_i$ sarebbe maggiore di n.
In realtà se $a_j=n$ ($b_j=c_j=0$) non può esistere un $a_i=n-1$ perché si avrebbe $b_i=0$ e $c_i=1$ (o viceversa) e $b_i=b_j$ che contraddice l'ipotesi.
Quindi N(n) è massimo n.

[ndp15]

Possono esistere al massimo $n+1$ $a_i$. Altrimenti o avremmo due $a_i$ uguali o un $a_i$ sarebbe maggiore di n.
In realtà se $a_j=n$ ($b_j=c_j=0$) non può esistere un $a_i=n-1$ perché si avrebbe $b_i=0$ e $c_i=1$ (o viceversa) e $b_i=b_j$ che contraddice l'ipotesi.
Quindi N(n) è massimo n.

Quindi?