2026-360

Sophia is collecting stickers for the 2026 World Cup album. To complete her collection, she plans to leave home (V0), visit all the sticker exchange points (V1, V2, V3, V4) in the city of Campinas exactly once, and then return home. The figure below shows a weighted adjacency matrix of an undirected graph.

	V0	V1	V2	V3	V4
V0	0	14	16	0	0
V1	14	0	11	12	14
V2	16	11	0	14	17
V3	0	12	14	0	15
V4	0	14	17	15	0

• each vertex (V) represents a sticker exchange point; 
• each link represents the possibility of traveling between two points; 
• the weight of each edge represents the amount Sophia will spend in R$ when taking that route; 
• there is only a connection between two vertices when the weight shown in the matrix is greater than zero. 

Considering this information, help Sophia choose a route where she visits all the sticker exchange points exactly once, returns home, and has the lowest possible total cost.

What is the minimum-cost cycle for Sophia? 

a) V0 -> V1 -> V2 -> V3 -> V4 -> V1 -> V0.

b) V0 -> V1 -> V3 -> V4 -> V2 -> V0.

c) V0 -> V2 -> V1 -> V3 -> V4 -> V1 -> V0.

d) V0 -> V2 -> V3 -> V4 -> V1 -> V0.

e) None of the above.

Original idea by: Tássia Martins

2026-359

A research team is modeling the spread of a highly contagious pathogen in a densely packed, fully connected community where the homogeneous mixing assumption holds. 

Because they are modeling the disease beyond its initial early stages, they cannot use the simple exponential approximation. Instead, they use the exact SI model equation:

i(t)=i0exp(βt)1−i0+i0exp(βt)

At the start of the observation (t=0), exactly 10% of the population is infected (i0=0.1). After a certain number of days t, the infection's exponential growth factor reaches eβt=9.

What is the fraction of infected individuals i(t) in the population at this time?

a) 81.8%

b) 33.3%

c) 10.0%

d) 50.0%

e) None of the above.

Original idea by: Matheus de Oliveira Saldanha

2026-358

Consider a Euclidian TSP with 5 cities located in a 2D plane at the following coordinates:

A (1, 2); B (5, 3); C (6, 7); D (2, 8); E (4, 5).

A delivery starts at city A and uses Nearest Neighbor Heuristic to construct a complete tour. Which alternative represents the total distance (cost) of the resulting tour, rounded to two decimals?

a) 13.31

b) 17.16

c) 15.52

d) 19.39

e) None of the above

Original idea by: Matheus Rufino

2026-357

When modeling the spread of a pathogen or an information cascade, the choice between the SI, SIS, and SIR compartmental frameworks depends entirely on the biological or behavioral traits of the agents involved. Under the homogeneous mixing assumption, each of these three classical models leads to a fundamentally different outcome in its final regime.

Which of the following statements correctly identifies the long-term behavior (final regime) of the SIR model and explains how it differs from the SI and SIS models?

A) In the SIR model, the fraction of infected individuals eventually drops to zero because infected individuals transition into a removed state where they develop permanent immunity or die.

B) The SIR model is the only framework where the entire population eventually ends up infected at the same time, unlike the SIS model which always maintains a mix of healthy and sick individuals.

C) In the final regime of the SIR model, the system reaches a steady endemic state where a fixed, non-zero fraction of the population remains actively infected forever.

D) The SIR model differs because it completely lacks an initial exponential growth regime, making its spread linear and predictable from day one.

E) None of the above.

Original idea by: Maria Luiza Ramos da Silva

2026-356

Regarding the relationships among cliques, strong communities, and weak communities, which of the following statements is correct?

1. Every weak community is a strong community
2. Every clique is a strong community, regardless of the external degrees of its nodes
3. Every \(n\)-clique is a strong community only if the external degree of every node in the clique is smaller than \(n\)
4. Every clique is a weak community, but no clique can be a strong community
5. None of the above

Original idea by: Giuliano Macedo.

2026-355

Analyze the following statements about the Agglomerative (Ravasz) and Divisive (Girvan–Newman) hierarchical clustering algorithms, and determine whether each statement is True (T) or False (F):

 1) The Agglomerative algorithm starts by treating each node in the network as an individual community and repeatedly merges the most similar communities until a stopping condition is reached. This stopping condition occurs when the density inside each community becomes maximal.

2) The Divisive algorithm follows a top-down strategy: it initially treats the entire network as a single community and progressively splits the network into smaller communities.

3) The result of the Agglomerative algorithm depends on the linkage criteria adopted (single, complete, or average linkage).

4) In the Girvan–Newman algorithm, communities are identified by iteratively removing links with high centrality, since these links are more likely to connect different communities.

5) In the Agglomerative hierarchical clustering, once two communities are merged, the algorithm may later separate them again if a stronger similarity pattern is detected.

Choose the correct alternative:

A) F-T-T-F-F

B) T-T-T-F-F

C) F-T-T-T-F

D) F-T-T-T-T

E) None of the above

Original idea by: Gabriela Caspa

2026-354

Consider the following adjacency matrix of an undirected network

$$A=
  \begin{bmatrix}
  0&1&1&0&0&0&0\\
  1&0&1&1&0&0&0\\
  1&1&0&1&1&0&0\\
  0&1&1&0&0&1&0\\
  0&0&1&0&0&1&1\\
  0&0&0&1&1&0&1\\
  0&0&0&0&1&1&0
  \end{bmatrix}$$

Consider the candidate communities 

$$C_1=\{1,2,3,4\}
  \qquad
  C_2=\{5,6,7\}$$

Which statement is correct?

1. \(C_1\) is a clique and \(C_2\) is a strong community
2. \(C_1\) is a strong community but not a clique, while \(C_2\) is a clique
3. Both \(C_1\) and \(C_2\) are strong communities but not cliques
4. \(C_1\) is a weak but not strong community and \(C_2\) is a clique
5. None of the above

Original idea by: Antonio De Cesare Del Nero