The Path Problem of Business Cards Exchange
Abstract
This article shows any solution in the path problem of business cards exchange is equal to any Latin square in the situation, which the total number of people participating in this activity is even.
The following awesome video shows how complex that people exchange their business cards with others.
After watching the video, I found the total number of times in exchanging business card is equal to the total number of links in complete graph [1]. (like the image below)
A complete graph has a feature that every node in the graph connects to any other nodes with a link.
The formula for calculating the total links is :
For example, a 3-vertice complete graph has 3 edges according to the formula above. (Yes, the graph is a triangle. Therefore the number of total edges in a complete graph is also called "Triangular number" [2])
The actual meaning of an edge between two nodes is a time of cards exchange. A complete graph makes sure each person exchanges its card with each other and the total times of exchange are minimum.
This paragraph below is to prove the Abstract paragraph above is correct.
Proof
The path problem of business cards exchange and Latin square [3] problem are equivalence in the situation, which the total number of people participating in this activity is even.
During card exchange, two guys exchange their cards with each other in each round.
Give a sequence of unique numbers to those cards and the unique number for each card demonstrates which person the card sources from. For example: No 1, 2, 3, ... come from people 1, people 2, people 3, ... as follow.
- If there is odd number totally, this case leaves one person nobody is able to exchange with in each round. ([all odd numbers] mod 2 = 1)
- In the same round of each person, there is no duplicate card exchanged. So I can take the attribute "round" as the column of a matrix.
- The total number of people is 'n'. Each person needs to exchange its card with other (n - 1) people at least to get all cards. There is still no duplicate people for each other to exchange with in each round. So I can take the attribute "people" as the row of a matrix.
- Therefore I can also take each person himself as round zero. It means each person has his own card in the round zero.
- The definition of matrix and Latin square are equivalence.
In case of n = 2, the Latin square and the solution is :
In case of n = 4 :
In case of n = 6:
... as follow
To make the matrix better to understand, so move “Round Zero” out of left bracket and next to the word "people". For example in case of 6:
One more thing ...
There is an unique solution like Sudoku [4] in case of assigning a specific path to people. For example let “people 1” exchange his card with “people 2”, “people 3” … “people n” sequentially and fulfill the condition of Sudoku.
Thanks for your reading.
Reference
[1] Complete Graph, Wikipedia, https://en.wikipedia.org/wiki/Complete_graph
[2] Triangular number, Wikipedia,
https://en.wikipedia.org/wiki/Triangular_number
[3] Latin Square, Wikipedia,
https://en.wikipedia.org/wiki/Latin_square
[4] Sudoku, Wikipedia,
https://en.wikipedia.org/wiki/Sudoku
If you like this article, please feel free to follow me.
See you next time.