Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>So there are <em>k=55</em> cards containing <em>m=8</em> pictures each from a pool of <em>n</em> pictures total. We can restate the question 'How many pictures <em>n</em> do we need, so that we can construct a set of <em>k</em> cards with only one shared picture between any pair of cards?' equivalently by asking:</p> <blockquote> <p>Given an <em>n</em>-dimensional vector space and the set of all vectors, which contain exactly <em>m</em> elements equal to one and all other zero, how big has <em>n</em> to be, so that we can find a set of <em>k</em> vectors, whose pairwise dot products are all equal to <em>1</em>?</p> </blockquote> <p>There are exactly (<em>n</em> choose <em>m</em>) possible vectors to build pairs from. So we at least need a big enough <em>n</em> so that (<em>n</em> choose <em>m</em>) >= <em>k</em>. This is just a lower bound, so for fulfilling the pairwise compatibility constraint we possibly need a much higher <em>n</em>.</p> <p>Just for experimenting a bit i wrote a small Haskell program to calculate valid card sets:</p> <p><strong>Edit:</strong> I just realized after seeing Neil's and Gajet's solution, that the algorithm i use doesn't always find the best possible solution, so everything below isn't necessarily valid. I'll try to update my code soon.</p> <pre class="lang-hs prettyprint-override"><code>module Main where cardCandidates n m = cardCandidates' [] (n-m) m cardCandidates' buildup 0 0 = [buildup] cardCandidates' buildup zc oc | zc&gt;0 &amp;&amp; oc&gt;0 = zerorec ++ onerec | zc&gt;0 = zerorec | otherwise = onerec where zerorec = cardCandidates' (0:buildup) (zc-1) oc onerec = cardCandidates' (1:buildup) zc (oc-1) dot x y = sum $ zipWith (*) x y compatible x y = dot x y == 1 compatibleCards = compatibleCards' [] compatibleCards' valid [] = valid compatibleCards' valid (c:cs) | all (compatible c) valid = compatibleCards' (c:valid) cs | otherwise = compatibleCards' valid cs legalCardSet n m = compatibleCards $ cardCandidates n m main = mapM_ print [(n, length $ legalCardSet n m) | n&lt;-[m..]] where m = 8 </code></pre> <p>The resulting maximum number of compatible cards for <em>m</em>=8 pictures per card for different number of pictures to choose from <em>n</em> for the first few <em>n</em> looks like this:</p> <p><img src="https://i.stack.imgur.com/dp1eI.png" alt=""></p> <p>This brute force method doesn't get very far though because of combinatorial explosion. But i thought it might still be interesting.</p> <p>Interestingly, it seems that for given <em>m</em>, <em>k</em> increases with <em>n</em> only up to a certain <em>n</em>, after which it stays constant.</p> <p>This means, that for every number of pictures per card there is a certain number of pictures to choose from, that results in maximum possible number of legal cards. Adding more pictures to choose from past that optimal number doesn't increase the number of legal cards any further.</p> <p>The first few optimal <em>k</em>'s are:</p> <p><img src="https://i.stack.imgur.com/nmZxw.png" alt="optimal k table"></p>
    singulars
    1. This table or related slice is empty.
    1. POWhat are the mathematical/computational principles behind this game?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USThies Heidecke
    1. USThies Heidecke
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat's just an initial attempt at a bound, right? You have not incorporated the "pairwise dot products equal to 1" requirement...
      singulars
      1. PO
      1. USNemo
    2. COyes, it's just a lower bound, not the maximum lower bound.
      singulars
      1. PO
      1. USThies Heidecke
    3. COApparently the syntax highlighter here doesn't really support Haskell *yet* (http://meta.stackexchange.com/questions/78363/manually-specify-language-for-syntax-highlighting), but I'll toss in the hint just in case it does in future.
      singulars
      1. PO
      1. USBoltClock
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload