A Game of "Society"

Here I have attached a document presenting my solution to the following problem, which was asked in  IISc  Bangalore’s  2020  Pravega  event  :  "Gaussian Gambit". Specifically, the last  question  of  Problem Set 1  : 

"A group  of  n  students  in  a  classroom are playing  a game of  ‘Society’.  Each student has  some friends  (possibly  none), and  friendship  is  mutual.  Every student begins  with  an  integral  amount of  dollars  (possibly  negative). A  move consists  of  some student giving  $1  to each  of  their  friends.  We say  that the game is  fair  if  it is  possible to  transform  the original  distribution  of  money  into any  other  arbitrary  one with  the same amount of  total  money  using  some finite sequence of  moves. Given  that  the game  is  fair, find  the number  of friendships  among  the students."

I have constructed my solution from the ground up, without directly using any results from Graph theory or Group theory. I have come to learn that this can be solved using a result of graph theory known as the Matrix Tree Theorem.  

https://documentcloud.adobe.com/link/review?uri=urn:aaid:scds:US:c53f5893-cd69-416c-8ea3-97a5c3a2cdb8 

Comments

Post a Comment

Popular posts from this blog

The Incentre of a Tetrahedron

Image
 Finding the Incentre (and Excentres) of a  Tetrahedron using Geometric arguments This is something I thought of mid-2020 during my JEE prep. Did not publish it then due to lack of time/ideas where to share it.  I am going to assume things like the existence (and uniqueness) of incentres and excentres, which I think should be true for all tetrahedrons. Notation :  Consider a tetrahedron (the bounded region enclosed by 4 non-parallel planes in  ℝ³ ,  such that any 3 of these planes intersect at a distinct point, basically an arbitrary triangular pyramid) .  Label each of the vertices as 1,2,3,4, and the opposite plane face to each vertex with the  same number  as the vertex. I.e, plane "i" is opposite to vertex "i". The Conventional Approach If you are familiar with Analytical (or "Coordinate") Geometry, this problem should look fairly straightforward - solve the following system in (x,y,z,r) : abs( aᵢx + bᵢy + cᵢz +dᵢ )/{ (aᵢ² + bᵢ² + cᵢ²)^½ ...
Read more

The MUB Project

 I will be updating this post regarding my project work. All the orange words are links! 1) Initial report  2) MASAs and MUBs - Part 1 (edited) This report isn't complete or self contained but it is my summary of the sections of Andras Szanto's paper [here] that I found relevant to the problem. There is no original contribution from my end in either this or the previous writeup, they are only meant to clarify terminology and set the stage. Some large updates coming soon! (1 Jan 2023) Said update : I am about 11 months late to post this, but attached below is some code (in MATLAB. I am truly sorry, some array operations are just way more convenient here) I wrote to show, essentially by brute force, that all classes of weakly unextendible MASAs belong to a complementary decomposition that satisfies Szanto's criterion. See this report explaining that monstrosity of a program and some interesting findings. I hope to actually improve the speed of this program and therefore...
Read more

QM Notes (Shankar)

  Notes on Chapter 14 of R.Shankar's QM -- Notes on Chapters 12 and 13 of R.Shankar's QM : Part 1 Part 2  (problems mostly) Hydrogen Atom -- Notes  on Chapter 11 of R.Shankar's QM. -- Notes  on Chapter 10 of R.Shankar's QM
Read more