Hm: "qualquer uma das 2021 possui voo direto", assim mesmo? Tenho ideias, mas tem que completar.
Vou dizer que uma marcação "cuida" de uma cidade X quando existe alguma cidade marcada com voo direto para X. Observe que, interpretando ao pé da letra o enunciado, X não necessariamente cuida de X! LEMA 1: Para um grafo do tipo "filete", Y1-Y2-...-YN conectadas em linha, N>=3, o número mínimo f(N) de cidades marcadas satisfaz f(N)<=2N/3. Mais: se N não é divisível por 3, podemos "economizar mais uma marcação" para obter f(N)<2N/3. Prova: -- Para N=3, marque Y1Y2, portanto f(3)<=2. -- Para N=4, marque Y2Y3, portanto f(4)<=2<8/3. -- Para N=5, marque Y2Y3Y4, portanto f(5)<=3<10/3. -- Para N=6, marque Y1Y2Y4Y5, portanto f(6)<=4. -- Para N=7, marque Y2Y3Y5Y6 portanto f(7)<=4<14/3. -- Para N=8, marque Y2Y3Y6Y7, portanto f(8)<=4<16/3. ... Em geral, para N>=6, a marcação depende do resto de N na divisão por 3: i) Se N=3k, divida as cidades em grupos de 3 e marque as 2 primeiras de cada grupo: note que cada 2 cidades "cuidam" do seu grupo de 3, portanto f(N)<=2N/3. ii) Se N=3k+1, separe Y1, e divida **as outras** em grupos de 3; novamente, marque as 2 primeiras de cada grupo (note que Y2 cuida de Y1!): f(N)<=2(N-1)/3<2N/3. iii) Se N=3k+2, separe as 5 primeiras e divida o resto em grupos de 3; marque Y2Y3 e as 2 primeiras de cada grupo (observe que Y6 cuida de Y5). Assim f(N)<=2(N-5)/3+2<2N/3. (Obs: de fato, para N grande, o ideal se parece mais com f(N)~~N/2: divida em grupos de 4, escolha as duas cidade do meio em cada grupo.) ---///--- Isso me faz desconfiar que o pior caso seria algo do tipo 2N/3, se tivermos filetes de tamanho 3 ou 6. Assim fica fácil construir um exemplo onde ~~2N/3 seria necessário: ---///--- LEMA 2: k>=(2/3)*2021-1, ou seja, k>=1347. Prova. Considere o caso onde as cidades são A, B1, B2, ..., B673, C1, C2, ..., C673, D1, D2, ..., D673, Z. Conecte apenas assim: -- A conecta com Z; -- A conecta com Bi para todo i; -- Bi conecta com Ci para todo i; -- Ci conecta com Di para todo i. Em suma, uma cidade "central" A, donde saem 673 filetes de comprimento 3 (e mais um filetezinho para conectar com a cidade que sobrou). Para cuidar de Di, temos que marcar Ci. Para cuidar de Ci, temos que marcar Bi ou Di (sendo esperto, escolhemos pelo menos um Bi para cuidar de A); para cuidar de Z temos que marcar A. Em suma, neste caso, a marcação deve ter pelo menos 673*2+1=1347 cidades. ---///--- Agora o que eu queria fazer era dividir o grafo em vários "filetes" *disjuntos*, e em cada filete fazer uma marcação com 2/3 dos vértices daquele filete, cuidando daquele filete. Juntando tudo, teríamos 2/3 dos vértices marcados; como pelo menos um filete teria numero de vértices não divisível por 3, eu "economizaria" uma marcação nele, chegando aos 1347. O problema seria garantir que esses filetes tem comprimento >=3 para poder usar o 2N/3... Se ficarmos com filetes de tamanho 1 ou 2, f(2)=2 estraga tudo (para o de comprimento 1, também teríamos problemas). Então minha ideia não funciona assim direto. Mas talvez ajude a pensar, ou achar um pior caso que seja pior que a minha "estrela" ali em cima... Abraço, Ralph. On Sat, May 23, 2020 at 11:46 AM Jeferson Almir <jefersonram...@gmail.com> wrote: > Amigos peço ajuda nesse problema, ou até algum resultado de grafos que > resolva. > > Terra Brasilis possui 2021 cidades, e existem voos de ida e volta entre > algumas dessas cidades de maneira que é possível chegar a qualquer outra > através de voos finitos. Encontre o menor inteiro positivo k tal que, > independente da configuração dos voos, é possível escolher k cidades de > modo que qualquer uma das 2021 cidades possui voo direto para alguma das > cidades marcadas. > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
