Odd number of pigs in cages

[jimoo]

A farmer asks you to build 4 changes to hold his 9 pigs and he wants to you put an odd number of pigs in each cage. Each cage must contain at least 1 pig. How can you do that?



Jim

 

[karluk]

I don't disagree that they are all separate solutions, assuming that the question is "How many total arrangements of pigs and cages are there?" They just aren't separate solutions to the question of "How many distinct cage topologies are there?"

To me it's much preferable to address the cage topology issue first, and only then proceed to work out the total number of solutions. It's just a good way to organize one's work. As far as I know, my tentative answer from yesterday about total arrangements of pigs and cages was correct, albeit incomplete. At the time I had missed some of the possible topologies, so I also missed all the arrangements of pigs and cages that correspond to the missing topologies.

 

[CajunCenturion]

The are separate solutions to the puzzle. They're not separate cage topologies.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

Opinion please:

If the cages intersect how would the quantity be counted?

e.g. 2 Cages intersect as below. Would this be counted as 2 Cages or 5?[tt]

---
| |
| |
-------------
| | | |
-------------
| |
| |
---[/tt]

**********************************************
What's most important is that you realise ... There is no spoon.

 

[CajunCenturion]

I would count each fully enclosed space as a cage. If you can from the center area to any of the outside areas, then there is only one fully enclosed space. I would count that as only one cage. If you cannot get from the center area to any of the outside area, then you have five fully enclosed spaces.

--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[kwbMitel]

Thanks CC, that's the way I see it too but it never hurts to ask.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[SamBones]

The way I read the original post, pig placement is part of the question.

A farmer asks you to build 4 changes to hold his 9 pigs and he wants to you put an odd number of pigs in each cage. Each cage must contain at least 1 pig.

How can you do that?

Yes, you are being asked to build four cages, but you are also being asked to place pigs in them so their numbers in each cage are odd. To me, the pig placement is clearly part of the problem and therefore the various pig placement solutions are important. The "How can you do that?" is vague enough to include the pig arrangements.

It's not just, "How many ways can you arrange four cages."

Well, as I do many times at work when there's a disagreement about requirements, we should go ask the farmer!

 

[SamBones]

Just looking purely at cage topologies, I made an interesting observation. Here is a list of all cage topologies, regardless of whether pigs can be placed to meet the requirements or not. This is just, "How many ways can you arrange four cages?" (my numbering is a little different than the list above.)
[tt]
1. [[[[]]]]
2. [[ [] [] ]]
3. [ [[]] [] ]
4. [ [] [] [] ]
5. [ [] [] ] [] <-- No Solution
6. [[[]]] [] <-- No Solution
7. [[]] [[]] <-- No Solution
8. [[]] [] []
9. [] [] [] [] <-- No Solution
[/tt]
My observation is, for there to be a solution, you must see an odd number of cages when viewed from the outside (assume they are opaque and completely hide any inner cages.

In topologies 1 through 4, you only see one cage from the outside. They all have solutions. Topologies 5, 6, and 7, you see two cages from the outside. They have no solutions. Topology 8 is viewed as three cages from the outside and has solutions. Topology 9 is seen as four cages, and there are no solution.

So, just a generalization for the problem, if you see an even number of cages from the outside, there is no solution.

This also validates karluk's list as being all of the cage topologies with valid solutions.

 

[karluk]

Here is (what I hope is) a complete list of solutions, grouped by cage topology. It's moderately long, but in my opinion not too long to include in its entirety in this thread.

Spoiler

topology 1: (13 solutions)
1. {{7}}, {1}, {1}
2. {{5}, 2}, {1}, {1}
3. {{3}, 4}, {1}, {1}
4. {{1}, 6}, {1}, {1}
5. {{5}}, {3}, {1}
6. {{3}, 2}, {3}, {1}
7. {{1}, 4}, {3}, {1}
8. {{3}}, {5}, {1}
9. {{1}, 2}, {5}, {1}
10. {{3}}, {3}, {3}
11. {{1}, 2}, {3}, {3}
12. {{1}}, {7}, {1}
13. {{1}}, {5}, {3}

topology 2: (35 solutions)
14. {{{{9}}}}
15. {{{{7}, 2}}}
16. {{{{7}}, 2}}
17. {{{{7}}}, 2}
18. {{{{5}, 4}}}
19. {{{{5}}, 4}}
20. {{{{5}}}, 4}
21. {{{{5}, 2}, 2}}
22. {{{{5}, 2}}, 2}
23. {{{{5}}, 2}, 2}
24. {{{{3}, 6}}}
25. {{{{3}}, 6}}
26. {{{{3}}}, 6}
27. {{{{3}, 4}, 2}}
28. {{{{3}, 4}}, 2}
29. {{{{3}}, 4}, 2}
30. {{{{3}, 2}, 4}}
31. {{{{3}, 2}}, 4}
32. {{{{3}}, 2}, 4}
33. {{{{3}, 2}, 2}, 2}
34. {{{{1}, 8}}}
35. {{{{1}}, 8}}
36. {{{{1}}}, 8}
37. {{{{1}, 6}, 2}}
38. {{{{1}, 6}}, 2}
39. {{{{1}}, 6}, 2}
40. {{{{1}, 2}, 6}}
41. {{{{1}, 2}}, 6}
42. {{{{1}}, 2}, 6}
43. {{{{1}, 4}, 4}}
44. {{{{1}, 4}}, 4}
45. {{{{1}}, 4}, 4}
46. {{{{1}, 4}, 2}, 2}
47. {{{{1}, 2}, 4}, 2}
48. {{{{1}, 2}, 2}, 4}

topology 3: (7 solutions)
49. {{7}, {1}, {1}}
50. {{5}, {3}, {1}}
51. {{5}, {1}, {1}, 2}
52. {{3}, {3}, {3}}
53. {{3}, {3}, {1}, 2}
54. {{3}, {1}, {1}, 4}
55. {{1}, {1}, {1}, 6}

topology 4: (13 solutions)
56. {{{7}, {1}, 1}}
57. {{{5}, {3}, 1}}
58. {{{5}, {1}, 3}}
59. {{{5}, {1}, 1}, 2}
60. {{{3}, {3}, 3}}
61. {{{3}, {3}, 1}, 2}
62. {{{3}, {1}, 5}}
63. {{{3}, {1}, 3}, 2}
64. {{{3}, {1}, 1}, 4}
65. {{{1}, {1}, 7}}
66. {{{1}, {1}, 5}, 2}
67. {{{1}, {1}, 3}, 4}
68. {{{1}, {1}, 1}, 6}

topology 5: (19 solutions)
69. {{{7}}, {1}, 1}
70. {{{5}}, {3}, 1}
71. {{{5}}, {1}, 3}
72. {{{5}, 2}, {1}, 1}
73. {{{3}}, {5}, 1}
74. {{{3}}, {1}, 5}
75. {{{3}}, {3}, 3}
76. {{{3}, 2}, {3}, 1}
77. {{{3}, 2}, {1}, 3}
78. {{{3}, 4}, {1}, 1}
79. {{{1}}, {7}, 1}
80. {{{1}}, {1}, 7}
81. {{{1}}, {5}, 3}
82. {{{1}}, {3}, 5}
83. {{{1}, 2}, {5}, 1}
84. {{{1}, 2}, {1}, 5}
85. {{{1}, 4}, {3}, 1}
86. {{{1}, 4}, {1}, 3}
87. {{{1}, 6}, {1}, 1}

 

[karluk]

Pretty funny. I left out my sample solution for topology 5 from my earlier post. So there is at least one addition needed to make the list complete. Can anyone find any others?

Spoiler

additional solution for topology 5:
88. {{{1}, 2}, {3}, 3}

 

[lionelhill]

SamBones' point is important.

Sam's making a slightly more general point than "If you make an integer division of an odd number by an even number, there will always be an odd remainder", and it's this odd remaining pig, which, when added to any even-number-divided set of pigs, leads to one group of pigs containing an odd number of pigs. This is always true.

Incidentally, if you divide an even number of objects by an odd number, there will also be an odd remainder. This is also always true. It means we could have dealt with the situation of 10 pigs in 5 cages.

Since Sam's observation is true not only of the outermost cage, but also of inner sets of cages, it can be used to test any arrangement of cages for pig-worthiness. If you open the door to a cage, and see within it an even number of cages, then this topology won't work.

At a glance, it's obvious that Sam's topologies 2 and 3 have no solutions.

 

[karluk]

If you open the door to a cage, and see within it an even number of cages, then this topology won't work.

Not true. This line of reasoning is tempting but wrong. It's the same mistake that OlafDoschke made earlier and is also the main reason I missed some of the possible cage topologies in my initial analysis of the problem.

At a glance, it's obvious that Sam's topologies 2 and 3 have no solutions.

Not as obvious as you think. If you check my list of solutions, there are dozens of solutions that use these two topologies.

 

[SamBones]

Since Sam's observation is true not only of the outermost cage, but also of inner sets of cages, it can be used to test any arrangement of cages for pig-worthiness. If you open the door to a cage, and see within it an even number of cages, then this topology won't work.

Not quite true because on inner cages you can have lone pigs walking around those even number of cages, as long as they are enclosed in a bigger cage. This makes solutions for topologies 2 and 3 possible.

These topologies below have no solutions since there is an even number of cages when viewed from the outside. This is for two reasons, you can't have pigs roaming around outside, and you can't have an even number of odd numbers that add up to 9.
[tt]
5. [ [] [] ] [] <-- No Solution, 2 cages when viewed from the outside
6. [[[]]] [] <-- No Solution, 2 cages when viewed from the outside
7. [[]] [[]] <-- No Solution, 2 cages when viewed from the outside
9. [] [] [] [] <-- No Solution, 4 cages when viewed from the outside
[/tt]
Since this is Puzzles for Programmers, I wrote a little C program that prints out all of the possibilities. All pig permutations for each cage topology. According to my program, which I admit could have errors, karluk's list is correct.

 

[SamBones]

Here's the output of my program. And I'm not enclosing it in spoiler tags because anyone that has gotten this far in the thread already knows the "trick" of enclosing cages in other cages. It's not really spoiling anything to put it in plain view.

In the output, for the topology, a "P" indicates a possible pig position. A solution like "{{1} 0}, {5}, {3}" would be the same as "{{1}} {5} {3}". The zero is still displayed since I didn't have time to add in zero suppression to my quick and dirty program.

$ ./pigs
Topology 1: {{P} P} {P} {P}
1.      {{1} 0}, {5}, {3}
2.      {{1} 0}, {7}, {1}
3.      {{1} 2}, {3}, {3}
4.      {{1} 2}, {5}, {1}
5.      {{1} 4}, {3}, {1}
6.      {{1} 6}, {1}, {1}
7.      {{3} 0}, {3}, {3}
8.      {{3} 0}, {5}, {1}
9.      {{3} 2}, {3}, {1}
10.     {{3} 4}, {1}, {1}
11.     {{5} 0}, {3}, {1}
12.     {{5} 2}, {1}, {1}
13.     {{7} 0}, {1}, {1}
13 solutions

Topology 2: {{{{P} P} P} P}
14.     {{{{1} 0} 0} 8}
15.     {{{{1} 0} 2} 6}
16.     {{{{1} 0} 4} 4}
17.     {{{{1} 0} 6} 2}
18.     {{{{1} 0} 8} 0}
19.     {{{{1} 2} 0} 6}
20.     {{{{1} 2} 2} 4}
21.     {{{{1} 2} 4} 2}
22.     {{{{1} 2} 6} 0}
23.     {{{{1} 4} 0} 4}
24.     {{{{1} 4} 2} 2}
25.     {{{{1} 4} 4} 0}
26.     {{{{1} 6} 0} 2}
27.     {{{{1} 6} 2} 0}
28.     {{{{1} 8} 0} 0}
29.     {{{{3} 0} 0} 6}
30.     {{{{3} 0} 2} 4}
31.     {{{{3} 0} 4} 2}
32.     {{{{3} 0} 6} 0}
33.     {{{{3} 2} 0} 4}
34.     {{{{3} 2} 2} 2}
35.     {{{{3} 2} 4} 0}
36.     {{{{3} 4} 0} 2}
37.     {{{{3} 4} 2} 0}
38.     {{{{3} 6} 0} 0}
39.     {{{{5} 0} 0} 4}
40.     {{{{5} 0} 2} 2}
41.     {{{{5} 0} 4} 0}
42.     {{{{5} 2} 0} 2}
43.     {{{{5} 2} 2} 0}
44.     {{{{5} 4} 0} 0}
45.     {{{{7} 0} 0} 2}
46.     {{{{7} 0} 2} 0}
47.     {{{{7} 2} 0} 0}
48.     {{{{9} 0} 0} 0}
35 solutions

Topology 3: {{P} {P} {P} P }
49.     {{1} {1} {1} 6}
50.     {{3} {1} {1} 4}
51.     {{3} {3} {1} 2}
52.     {{3} {3} {3} 0}
53.     {{5} {1} {1} 2}
54.     {{5} {3} {1} 0}
55.     {{7} {1} {1} 0}
7 solutions

Topology 4: {{{P} {P} P} P }
56.     {{{1} {1} 1} 6}
57.     {{{1} {1} 3} 4}
58.     {{{1} {1} 5} 2}
59.     {{{1} {1} 7} 0}
60.     {{{3} {1} 1} 4}
61.     {{{3} {1} 3} 2}
62.     {{{3} {1} 5} 0}
63.     {{{3} {3} 1} 2}
64.     {{{3} {3} 3} 0}
65.     {{{5} {1} 1} 2}
66.     {{{5} {1} 3} 0}
67.     {{{5} {3} 1} 0}
68.     {{{7} {1} 1} 0}
13 solutions

Topology 4: {{{P} {P} P} P }
69.     {{{1} 0} {1} 7}
70.     {{{1} 0} {3} 5}
71.     {{{1} 0} {5} 3}
72.     {{{1} 0} {7} 1}
73.     {{{1} 2} {1} 5}
74.     {{{1} 2} {3} 3}
75.     {{{1} 2} {5} 1}
76.     {{{1} 4} {1} 3}
77.     {{{1} 4} {3} 1}
78.     {{{1} 6} {1} 1}
79.     {{{3} 0} {1} 5}
80.     {{{3} 0} {3} 3}
81.     {{{3} 0} {5} 1}
82.     {{{3} 2} {1} 3}
83.     {{{3} 2} {3} 1}
84.     {{{3} 4} {1} 1}
85.     {{{5} 0} {1} 3}
86.     {{{5} 0} {3} 1}
87.     {{{5} 2} {1} 1}
88.     {{{7} 0} {1} 1}
20 solutions

 

[karluk]

Sam, you copied the line "Topology 4: {{{P} {P} P} P }" twice, so you don't have any topology 5 listed. That's probably just a cut-and-paste error, however. Other than that, it is very encouraging that you and I got the exact same number of solutions for each topology. Most likely 88 is the total number of solutions.

 

[SamBones]

Oops, sorry. That's just a cut and paste error on the Title Line for that topology. But, you'll notice that #69 through #88 are correct solutions for topology 5 (20 solutions).

I'm pretty sure it's complete and correct. It's a brute force program that tried every single combination of pigs from 0,0,0,0 to 9,9,9,9 in each topology, and just reported the topology if all cages held an odd number of pigs per cage and totaled 9 pigs.

The only thing that would change the result is if we found another topology. I only tested the five topologies that we decided had solutions.

 

[karluk]

In that case I'm ready to call the problem solved. 88 is a large enough number of solutions that it deserves a computer check. I'm much more willing to rely on human calculation of the number of topologies. We've looked at all of a rather small number of possibilities, and all but the obviously impossible topologies were found to have solutions.

 

[lionelhill]

ah, sorry, it was obvious, but obvious in a very different sense to what I saw!

The pig-herding rule is: If you are herding an odd number of pigs, and you open the door to a cage and see an even number of cages within it, you need to leave an odd number of pigs in the cage you are now entering, and split the remaining even number of pigs between the even number of cages... If you are herding an even number of pigs, and you see an odd number of cages, leave a pig where you are.

As I was typing, I had a feeling the point about dividing up even numbers was important, and not just "incidental" as I wrote. Thanks for the correction.

 

[SamBones]

] ] ] ] ] ] ] ] ]

Now we have to herd them? Sorry, count me out! I got into computers to avoid manual labor!

 

[Olaf Doschke]

What about complicating the problem with angry birds?

Bye, Olaf.

 

[Diancecht]

1.5 is considered an odd number? I don't see any problem on cutting some pigs into pieces

Cheers,
Dian