- B 10 Points We Are Trying To Fill A 10 By 10 Board Such That Each Row Contains Exactly One Of Each From 1 10 A 1 (67.49 KiB) Viewed 18 times
(b) (10 points) We are trying to fill a 10-by-10 board such that each row contains exactly one of each from {1,...,10} a
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
(b) (10 points) We are trying to fill a 10-by-10 board such that each row contains exactly one of each from {1,...,10} a
(b) (10 points) We are trying to fill a 10-by-10 board such that each row contains exactly one of each from {1,...,10} and each column contains at most one of each from the same set (Think Sudoku without the 3-by-3 block restraint). If the top 5-rows are already filled obeying this rule, prove that we can fill the next row so that this board satisfies the condition. (Hint : use Hall marriage theorem, in particular the Lemma introduced in class. Pick the left and right vertex set so the perfect matching here gives the way to fill the 5-th row correctly.)
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!