[IMO Shortlist 2013, C3]
A crazy physicist discovered a new kind of particle which he called an imon. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in the lab by creating a copy I’ of each imon I. During this procedure, the two copies I’ and J’ become entangled if and only if the original imons I and J are entangled, and each copy I’ becomes entangled with its original imon I; no other entanglements occur or disappear at this moment.
Show that after a finite number of operations, he can ensure that no pair of particles is entangled.
The imons and their cloning are better visualized with a data structure that represents the entanglements and the imons. We therefore use a graph with vertices as imons and edges as entanglements. Further, in order to differentiate every imon, we color them each differently. From graph coloring we know that a graph with n vertices can be colored with n colors so that every two connected vertices have different colors.
Now if we could reduce these colors to just one it would mean a graph with no edges – our desired goal.
In other words, our strategy is to assume a graph G that admits proper coloring for n colors so that no two connected vertices have different colors and then show that a sequence of operations can result in a graph which admits coloring of n-1.
To show this we do the following:
We repeatedly apply operation 1 to any appropriate vertices until there are no more. This reduces the number of vertices and results in a graph with all even edges. Since this is a subset, it will still honor a proper coloring in n colors. We fix the colorings.
Now we apply the second operation to the graph. This doubles the vertices but now we can still color them differently using n colors because for the new vertices around an original vertex of color k, we color them with k+1 mod n. The original vertices have different colors. Their clones also have different colors from the original now. Furthermore between the clones the coloring will be different because n > 1. And finally all the vertices have now od d number of edges. Therefore those vertices that have the color n can now be destroyed leaving the graph with coloring in n – 1 colors.
When we repeatedly reduce the colors with the above strategy, we are left with vertices and no edges as required.
#codingexercise
Print count of headers listed in a file
#include "stdafx.h"
#include "stdio.h"
#include "string.h"
static int Hash (const char * pSrc, size_t len);
int main(int argc, char* argv[])
{
static const char filename[] = "foo.txt";
static const int MAX_COUNT = 255;
static int frequency[MAX_COUNT] = {0};
FILE* fd = fopen(filename, "r");
if ( fd != NULL )
{
char line[MAX_COUNT + 1];
while ( fgets(line, sizeof line, fd) != NULL )
{
char* p = strchr(line, ':');
if (p != NULL)
{
frequency[Hash(_strlwr(line), (size_t)(p-line))%MAX_COUNT] += 1;
}
}
fclose(fd);
char header[MAX_COUNT + 1] = {0};
printf( "Enter the header:\n " );
scanf("%255s", header);
header[MAX_COUNT] = '\0';
printf( "%s occurs %d times.\n", header, frequency[Hash(_strlwr(header), strlen(_strlwr(header)))%MAX_COUNT] );
}
return 0;
}
static int Hash (const char * pSrc, size_t len)
{
size_t res = 0;
while (len--) res = (res << 1) ^ *pSrc++;
return (int)res;
}
If we want to print all headers by sorted order, we could do something like this:
#dirty
#codingexercise
Print count of headers listed in a file
#include "stdafx.h"
#include "stdio.h"
#include "string.h"
static int Hash (const char * pSrc, size_t len);
int main(int argc, char* argv[])
{
static const char filename[] = "foo.txt";
static const int MAX_COUNT = 255;
static int frequency[MAX_COUNT] = {0};
FILE* fd = fopen(filename, "r");
if ( fd != NULL )
{
char line[MAX_COUNT + 1];
while ( fgets(line, sizeof line, fd) != NULL )
{
char* p = strchr(line, ':');
if (p != NULL)
{
frequency[Hash(_strlwr(line), (size_t)(p-line))%MAX_COUNT] += 1;
}
}
fclose(fd);
char header[MAX_COUNT + 1] = {0};
printf( "Enter the header:\n " );
scanf("%255s", header);
header[MAX_COUNT] = '\0';
printf( "%s occurs %d times.\n", header, frequency[Hash(_strlwr(header), strlen(_strlwr(header)))%MAX_COUNT] );
}
return 0;
}
static int Hash (const char * pSrc, size_t len)
{
size_t res = 0;
while (len--) res = (res << 1) ^ *pSrc++;
return (int)res;
}
If we want to print all headers by sorted order, we could do something like this:
#dirty
typedef struct _headers {
char header[MAX_COUNT+1];
int hash;
int frequency;
} headers;
int comp (const header * elem1, const header * elem2)
{
int f = elem1->frequency;
int s = elem2->frequency;
if (f > s) return 1;
if (f < s) return -1;
return 0;
}
int main(int argc, char* argv[])
{
headers* x = (header*) malloc(MAX_COUNT * sizeof(headers));
memset((void*)x, 0, sizeof headers);
qsort (x, sizeof(x)/sizeof(*x), sizeof(*x), comp);
for (int i = 0 ; i < MAX_COUNT ; i++){
headers[i] = malloc(sizeof(struct headers));
// populate header and frequency
}
qsort (x, sizeof(x)/sizeof(*x), sizeof(*x), comp);
// print headers encountered in sorted order
for (int i = 0 ; i < MAX_COUNT ; i++){
if (x[i]){
printf("%s",x[i]->header);
}
}
return 0;
}
