Problem 1393. A (wrong) place for everything, and everything in its (wrong) place

Created by James

Solve Later

{"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":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You have an equal number of cups and balls, each labelled from one to N. You randomly place one ball in each cup. Determine the number of possible combinations such that no balls are in the cup with a matching number. For example, if you have three balls and three cups, there are two valid solutions:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>2, 3, 1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>3, 1, 2</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The following permutations do not meet the criteria for the reasons listed:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>1, 2, 3 (all three balls are in the correct cups)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>1, 3, 2 (ball 1 is in cup 1)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>3, 2, 1 (ball 2 is in cup 2)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>2, 1, 3 (ball 3 is in cup 3)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Good luck!</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

127 Solutions
48 Solvers

Last Solution submitted on Dec 31, 2022

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Jean-Marie Sainthillier on 8 Apr 2013

I think that with this kind of problem, you can process in two steps.
A first easy problem with small N (to test perms for example). And a harder problem with big N, which
oblige to find another algorithm.

Binbin Qi on 27 Oct 2014

http://oeis.org/A000166

Problem Recent Solvers48

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1393. A (wrong) place for everything, and everything in its (wrong) place

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers48

Suggested Problems

More from this Author80

Problem Tags

Community Treasure Hunt

Problem 1393. A (wrong) place for everything, and everything in its (wrong) place

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers48

Suggested Problems

More from this Author80

Problem Tags

Community Treasure Hunt

Players