1
   

The Harem Problem

 
 
RK4
 
Reply Sun 4 Dec, 2005 10:53 pm
Let B be a set of boys, and suppose that each boy in B wishes to marry more than one of his girl friends. Find a necessary and sufficient condition for the harem problem to have a solution.

I was thinking perhaps we need to somehow replace each boy by several identical copies of himself, and then try to use Hall's theorem. But how?
  • Topic Stats
  • Top Replies
  • Link to this Topic
Type: Discussion • Score: 1 • Views: 2,045 • Replies: 2
No top replies

 
fresco
 
  1  
Reply Mon 5 Dec, 2005 12:13 pm
http://www.inf.uni-konstanz.de/algo/lehre/ws02/gt/exercises/ex7.pdf

Hmmmm !
0 Replies
 
FreeDuck
 
  1  
Reply Mon 5 Dec, 2005 12:28 pm
I don't know Hall's theorem, but it seems you would want the size of G (the girls) to be greater than or equal to the size of B (the boys).
0 Replies
 
 

Related Topics

Evolution 101 - Discussion by gungasnake
Typing Equations on a PC - Discussion by Brandon9000
The Future of Artificial Intelligence - Discussion by Brandon9000
The well known Mind vs Brain. - Discussion by crayon851
Scientists Offer Proof of 'Dark Matter' - Discussion by oralloy
Blue Saturn - Discussion by oralloy
Bald Eagle-DDT Myth Still Flying High - Discussion by gungasnake
DDT: A Weapon of Mass Survival - Discussion by gungasnake
 
  1. Forums
  2. » The Harem Problem
Copyright © 2024 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 0.04 seconds on 09/29/2024 at 08:24:49