{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2026-05-26T00:16:20.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2026-05-26T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":2254,"title":"Possible Opponents Matrix for single-elimination tournament","description":"It's tournament time!\r\n\r\nGiven a single-elimination tournament with 2^N competitors, compute the 2^N by 2^N matrix M such that M(i,j)=1 iff competitor i might play competitor j in round R, where 1\u003c=R\u003c=N.  (In each round each surviving competitor plays his \"next door neighbor\" in the bracket.)\r\n\r\nFor example, if N=1, R=1 then\r\n\r\n M =\r\n   [ 0 1\r\n     1 0]\r\n\r\nor if N=2, R=2 then\r\n\r\n M = \r\n   [ 0 0 1 1 \r\n     0 0 1 1\r\n     1 1 0 0 \r\n     1 1 0 0 ]","description_html":"\u003cp\u003eIt's tournament time!\u003c/p\u003e\u003cp\u003eGiven a single-elimination tournament with 2^N competitors, compute the 2^N by 2^N matrix M such that M(i,j)=1 iff competitor i might play competitor j in round R, where 1\u0026lt;=R\u0026lt;=N.  (In each round each surviving competitor plays his \"next door neighbor\" in the bracket.)\u003c/p\u003e\u003cp\u003eFor example, if N=1, R=1 then\u003c/p\u003e\u003cpre\u003e M =\r\n   [ 0 1\r\n     1 0]\u003c/pre\u003e\u003cp\u003eor if N=2, R=2 then\u003c/p\u003e\u003cpre\u003e M = \r\n   [ 0 0 1 1 \r\n     0 0 1 1\r\n     1 1 0 0 \r\n     1 1 0 0 ]\u003c/pre\u003e","function_template":"function [ o ] = opponents( N , R )\r\n  o=zeros(2^N);\r\nend","test_suite":"1\r\n%%\r\no=opponents(1,1);\r\nassert(isequal(o,[0 1;1 0]))\r\n2\r\n%%\r\no=opponents(2,1);\r\nassert(isequal(o,[0 1 0 0;1 0 0 0;0 0 0 1;0 0 1 0]))\r\n3\r\n%%\r\no=opponents(2,2);\r\nassert(isequal(o,[0 0 1 1;0 0 1 1;1 1 0 0 ;1 1 0 0]))\r\n4\r\n%%\r\nfor w=1:5\r\n    N=randi(5);\r\n    R=randi(N);\r\n    o=opponents(N,R);\r\n    assert(isequal(size(o),[2^N 2^N]))\r\n    for v=1:10;\r\n        i=randi(2^N);\r\n        j=randi(2^N);\r\n        q=dec2bin([i;j]-1,N)-'0';\r\n        % i might face j in round R if they are identical\r\n        % in the leftmost N-R bits, but differ in the (N-R+1)th bit\r\n        assert(o(i,j)==(1==polyval(abs(diff(q(:,1:N-R+1))),2)))\r\n    end\r\nend\r\n","published":true,"deleted":false,"likes_count":3,"comments_count":6,"created_by":4567,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":12,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2014-03-23T17:48:43.000Z","updated_at":"2026-05-28T02:33:30.000Z","published_at":"2014-03-23T17:48:43.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eIt's tournament time!\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven a single-elimination tournament with 2^N competitors, compute the 2^N by 2^N matrix M such that M(i,j)=1 iff competitor i might play competitor j in round R, where 1\u0026lt;=R\u0026lt;=N. (In each round each surviving competitor plays his \\\"next door neighbor\\\" in the bracket.)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFor example, if N=1, R=1 then\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[ M =\\n   [ 0 1\\n     1 0]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eor if N=2, R=2 then\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[ M = \\n   [ 0 0 1 1 \\n     0 0 1 1\\n     1 1 0 0 \\n     1 1 0 0 ]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2697,"title":"Probability of winning single-elimination tournament","description":"Find the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup.  In the first round player 1 plays player 2, player 3 plays player 4 and so on.  (In each round each surviving competitor plays his surviving \"next door neighbor\" in the bracket.)\r\n\r\nSee also problem \u003c2254\u003e.\r\n\r\nTrivial example :\r\n\r\nif \r\n\r\n   \r\n\r\n  M = [ NaN 0.7 ; 0.3 NaN ]\r\n\r\nthen \r\n\r\n  winprob(M,1)=0.7 \r\n\r\nand \r\n\r\n  winprob(M,2)=0.3","description_html":"\u003cp\u003eFind the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup.  In the first round player 1 plays player 2, player 3 plays player 4 and so on.  (In each round each surviving competitor plays his surviving \"next door neighbor\" in the bracket.)\u003c/p\u003e\u003cp\u003eSee also problem \u003ca href = \"2254\"\u003e2254\u003c/a\u003e.\u003c/p\u003e\u003cp\u003eTrivial example :\u003c/p\u003e\u003cp\u003eif\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003eM = [ NaN 0.7 ; 0.3 NaN ]\r\n\u003c/pre\u003e\u003cp\u003ethen\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ewinprob(M,1)=0.7 \r\n\u003c/pre\u003e\u003cp\u003eand\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ewinprob(M,2)=0.3\r\n\u003c/pre\u003e","function_template":"function prob = winprob(M,p)\r\n  prob = 1;\r\nend","test_suite":"1\r\n%%\r\nM = [ NaN 1 ; 0 NaN ];\r\nassert(isequal(winprob(M,1),1));\r\nassert(isequal(winprob(M,2),0));\r\n\r\n2\r\n%%\r\nM = [ NaN 0.7 ; 0.3 NaN ];\r\nassert(isequal(winprob(M,1),0.7));\r\nassert(isequal(winprob(M,2),0.3));\r\n\r\n3\r\n%%\r\nM = zeros(8)+NaN;\r\nfor i=1:7\r\n    for j=i+1:8\r\n        r=rand();\r\n        M(i,j)=r;\r\n        M(j,i)=1-r;\r\n    end\r\nend\r\n\r\nepsilon=1e-8;\r\ntotprob=0;\r\nfor i=1:8\r\n    totprob=totprob+winprob(M,i);\r\nend\r\nassert(abs(totprob-1)\u003cepsilon);\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":2,"created_by":4567,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":7,"test_suite_updated_at":"2014-12-02T02:09:00.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2014-11-30T16:23:41.000Z","updated_at":"2026-05-28T04:17:48.000Z","published_at":"2014-11-30T16:23:41.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFind the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup. In the first round player 1 plays player 2, player 3 plays player 4 and so on. (In each round each surviving competitor plays his surviving \\\"next door neighbor\\\" in the bracket.)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eSee also problem\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"2254\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e2254\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTrivial example :\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eif\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[M = [ NaN 0.7 ; 0.3 NaN ]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003ethen\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[winprob(M,1)=0.7]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eand\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[winprob(M,2)=0.3]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"problem_search":{"problems":[{"id":2254,"title":"Possible Opponents Matrix for single-elimination tournament","description":"It's tournament time!\r\n\r\nGiven a single-elimination tournament with 2^N competitors, compute the 2^N by 2^N matrix M such that M(i,j)=1 iff competitor i might play competitor j in round R, where 1\u003c=R\u003c=N.  (In each round each surviving competitor plays his \"next door neighbor\" in the bracket.)\r\n\r\nFor example, if N=1, R=1 then\r\n\r\n M =\r\n   [ 0 1\r\n     1 0]\r\n\r\nor if N=2, R=2 then\r\n\r\n M = \r\n   [ 0 0 1 1 \r\n     0 0 1 1\r\n     1 1 0 0 \r\n     1 1 0 0 ]","description_html":"\u003cp\u003eIt's tournament time!\u003c/p\u003e\u003cp\u003eGiven a single-elimination tournament with 2^N competitors, compute the 2^N by 2^N matrix M such that M(i,j)=1 iff competitor i might play competitor j in round R, where 1\u0026lt;=R\u0026lt;=N.  (In each round each surviving competitor plays his \"next door neighbor\" in the bracket.)\u003c/p\u003e\u003cp\u003eFor example, if N=1, R=1 then\u003c/p\u003e\u003cpre\u003e M =\r\n   [ 0 1\r\n     1 0]\u003c/pre\u003e\u003cp\u003eor if N=2, R=2 then\u003c/p\u003e\u003cpre\u003e M = \r\n   [ 0 0 1 1 \r\n     0 0 1 1\r\n     1 1 0 0 \r\n     1 1 0 0 ]\u003c/pre\u003e","function_template":"function [ o ] = opponents( N , R )\r\n  o=zeros(2^N);\r\nend","test_suite":"1\r\n%%\r\no=opponents(1,1);\r\nassert(isequal(o,[0 1;1 0]))\r\n2\r\n%%\r\no=opponents(2,1);\r\nassert(isequal(o,[0 1 0 0;1 0 0 0;0 0 0 1;0 0 1 0]))\r\n3\r\n%%\r\no=opponents(2,2);\r\nassert(isequal(o,[0 0 1 1;0 0 1 1;1 1 0 0 ;1 1 0 0]))\r\n4\r\n%%\r\nfor w=1:5\r\n    N=randi(5);\r\n    R=randi(N);\r\n    o=opponents(N,R);\r\n    assert(isequal(size(o),[2^N 2^N]))\r\n    for v=1:10;\r\n        i=randi(2^N);\r\n        j=randi(2^N);\r\n        q=dec2bin([i;j]-1,N)-'0';\r\n        % i might face j in round R if they are identical\r\n        % in the leftmost N-R bits, but differ in the (N-R+1)th bit\r\n        assert(o(i,j)==(1==polyval(abs(diff(q(:,1:N-R+1))),2)))\r\n    end\r\nend\r\n","published":true,"deleted":false,"likes_count":3,"comments_count":6,"created_by":4567,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":12,"test_suite_updated_at":null,"rescore_all_solutions":false,"group_id":1,"created_at":"2014-03-23T17:48:43.000Z","updated_at":"2026-05-28T02:33:30.000Z","published_at":"2014-03-23T17:48:43.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eIt's tournament time!\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven a single-elimination tournament with 2^N competitors, compute the 2^N by 2^N matrix M such that M(i,j)=1 iff competitor i might play competitor j in round R, where 1\u0026lt;=R\u0026lt;=N. (In each round each surviving competitor plays his \\\"next door neighbor\\\" in the bracket.)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFor example, if N=1, R=1 then\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[ M =\\n   [ 0 1\\n     1 0]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eor if N=2, R=2 then\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[ M = \\n   [ 0 0 1 1 \\n     0 0 1 1\\n     1 1 0 0 \\n     1 1 0 0 ]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"},{"id":2697,"title":"Probability of winning single-elimination tournament","description":"Find the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup.  In the first round player 1 plays player 2, player 3 plays player 4 and so on.  (In each round each surviving competitor plays his surviving \"next door neighbor\" in the bracket.)\r\n\r\nSee also problem \u003c2254\u003e.\r\n\r\nTrivial example :\r\n\r\nif \r\n\r\n   \r\n\r\n  M = [ NaN 0.7 ; 0.3 NaN ]\r\n\r\nthen \r\n\r\n  winprob(M,1)=0.7 \r\n\r\nand \r\n\r\n  winprob(M,2)=0.3","description_html":"\u003cp\u003eFind the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup.  In the first round player 1 plays player 2, player 3 plays player 4 and so on.  (In each round each surviving competitor plays his surviving \"next door neighbor\" in the bracket.)\u003c/p\u003e\u003cp\u003eSee also problem \u003ca href = \"2254\"\u003e2254\u003c/a\u003e.\u003c/p\u003e\u003cp\u003eTrivial example :\u003c/p\u003e\u003cp\u003eif\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003eM = [ NaN 0.7 ; 0.3 NaN ]\r\n\u003c/pre\u003e\u003cp\u003ethen\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ewinprob(M,1)=0.7 \r\n\u003c/pre\u003e\u003cp\u003eand\u003c/p\u003e\u003cpre class=\"language-matlab\"\u003ewinprob(M,2)=0.3\r\n\u003c/pre\u003e","function_template":"function prob = winprob(M,p)\r\n  prob = 1;\r\nend","test_suite":"1\r\n%%\r\nM = [ NaN 1 ; 0 NaN ];\r\nassert(isequal(winprob(M,1),1));\r\nassert(isequal(winprob(M,2),0));\r\n\r\n2\r\n%%\r\nM = [ NaN 0.7 ; 0.3 NaN ];\r\nassert(isequal(winprob(M,1),0.7));\r\nassert(isequal(winprob(M,2),0.3));\r\n\r\n3\r\n%%\r\nM = zeros(8)+NaN;\r\nfor i=1:7\r\n    for j=i+1:8\r\n        r=rand();\r\n        M(i,j)=r;\r\n        M(j,i)=1-r;\r\n    end\r\nend\r\n\r\nepsilon=1e-8;\r\ntotprob=0;\r\nfor i=1:8\r\n    totprob=totprob+winprob(M,i);\r\nend\r\nassert(abs(totprob-1)\u003cepsilon);\r\n","published":true,"deleted":false,"likes_count":1,"comments_count":2,"created_by":4567,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":7,"test_suite_updated_at":"2014-12-02T02:09:00.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2014-11-30T16:23:41.000Z","updated_at":"2026-05-28T04:17:48.000Z","published_at":"2014-11-30T16:23:41.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFind the probability that the p^{th} player will win a single-elimination tournament with 2^n players where M(i,j)=probability that player i will beat player j in a head-to-head matchup. In the first round player 1 plays player 2, player 3 plays player 4 and so on. (In each round each surviving competitor plays his surviving \\\"next door neighbor\\\" in the bracket.)\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eSee also problem\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"2254\\\"\u003e\u003cw:r\u003e\u003cw:t\u003e2254\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eTrivial example :\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eif\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[M = [ NaN 0.7 ; 0.3 NaN ]]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003ethen\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[winprob(M,1)=0.7]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eand\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[winprob(M,2)=0.3]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"errors":[],"facets":[[],[{"value":"medium","count":2,"selected":false}]],"term":"tag:\"tournament\"","page":1,"per_page":50,"sort":"map(difficulty_value,0,0,999) asc"}}