Thursday, October 1, 2015

Proof by induction for the Olympiad question described below: 
[Czech and Slovak Republics 1997] 
Each side and diagonal of a regular n-gon (n ≥ 3) is colored blue or green. A move consists of choosing a vertex and switching the color of each segment incident to that vertex (from blue to green or vice versa). Prove that regardless of the initial coloring, it is possible to make the number of blue segments incident to each vertex even by following a sequence of moves. Also show that the final configuration obtained is uniquely determined by the initial coloring. 
In a polyhedron with n vertices, the total number of edges to form a complete graph is N = n(n-1)/2. 
For n=3, this is 3 edges (triangle) 
For n=4, this is 6 edges (four sides and two diagonals in a square) 
For n=5, this is 10 edges (five sides and five diagonals in a pentagon 
Due to symmetry, in all these cases each vertex has equal number of edges incident on it and these are the total number of edges connecting that vertex to the remaining vertex. 
Therefore the possible blue or green to a vertex can be 
(1, N - 1), (2, N-2), (3, N-3) … (N/2, N/2) if N is even or ((N+1)/2 - 1,(N+1)/2) if N is odd  
For each of the configurations we have (odd,even)(odd,odd)(even,odd)and(even,even) 
For (odd,even) we make one move and we can reverse the colors to a case where blue is even. For (even,even) with or without any moves the number remains even. For (odd, odd) we can show that alternate vertices can have (odd,even) leading to an exchange of exactly one edge shared with the (odd,odd) vertex causing it to change into one having odd, even. Note that there can be at most only one (odd,odd) or (even, even) in the set for any N and correspondingly at least one edge different from the rest in color. 
We use the same logic for formal proof by induction. We say let the facts be true for N. With the addition of one more vertex, we now have a configuration set as earlier but with the terminal changing (odd,even) to (odd,odd) or (even,even) and vice versa. 
Therefore the facts hold for N+1. 

#Technology
How do we transfer ownership of Buckets in AWS compatible S3 storage ?
Let us take a look at the ACL we can place on the bucket

$result = $client->putBucketAcl(array(
    'ACL' => 'string',
    'Grants' => array(
        array(
            'Grantee' => array(
                'DisplayName' => 'string',
                'EmailAddress' => 'string',
                'ID' => 'string',
                // Type is required
                'Type' => 'string',
                'URI' => 'string',
            ),
            'Permission' => 'string',
        ),
        // ... repeated
    ),
    'Owner' => array(
        'DisplayName' => 'string',
        'ID' => 'string',
    ),
    // Bucket is required
    'Bucket' => 'string',
    'GrantFullControl' => 'string',
    'GrantRead' => 'string',
    'GrantReadACP' => 'string',
    'GrantWrite' => 'string',
    'GrantWriteACP' => 'string',

));
and all we need are
1)  the canonical ID of the new owner as the Grantee, 
2)  the Permission as 'FULL_CONTROL' and 
3)  the name of the bucket.

The canonical ID can be retrieved as follows:
curl -i -k -u user:pass 'https://s3_endpoint_url\/user?userId=<newowner>&groupId=<team_id>'
which gives data 
 {"active":"true","userType":"GroupAdmin","fullName":"Ravi Rajamani","emailAddr":"rajamani@adobe.com","address1":"","address2":"","city":"Seattle","zip":"","phone":"","website":"","state":"Washington","country":"United States","groupId":"team1","userId":"rajamani","canonicalUserId":"db67c360ed6977kkkkkaf9cb43f9de64"}
and includes the canonical ID.

I tried this out and surprisingly the ACLs don't get applied as intended. On the other hand, the recommended practice is to copy the contents of the bucket from one to the other. 

No comments:

Post a Comment