Distributing צדקה In Polynomial Time

This post was inspired by Andy, a former computer science guy, and is dedicated to Dr. Pinhas Grossman, Marie Curie Research Fellow at Cardiff University.

In the course of a conversation with a friend of mine who collects מתנות לאביונים for distribution to several אביונים, the following question arose:

A number of donors contribute arbitrary amounts of money for distribution by a גבאי to two עניים. Each donor prefers that his entire donation be given exclusively to one עני. What is the optimal distribution of the funds, that minimizes the difference between the sums received by the two עניים?

Solving this by brute force is straightforward; here’s a Perl program to do it:

[perl]#! /usr/bin/perl -w

# Copyright (C) 2010 Yitzhak (celejar@gmail.com)
# Combin is free software, released under the terms of the Perl Artistic
# License: http://perldoc.perl.org/perlartistic.html
# Combin comes with ABSOLUTELY NO WARRANTY

# Combin finds the division of a set of numbers into two subsets, such
# that the difference between the sums of the numbers in the subsets is
# the smallest possible

# usage: combin [-n num [-m max]] [-v]

# If -n is not given, a series of numbers is read from STDIN. Otherwise,
# ‘num’ random numbers between 1 and ‘max’ (or 1024, if -m is not given)
# are generated. If -v is specified, Combin will print out interim minimal
# solutions.

use strict;
no warnings ‘recursion’;

use Getopt::Std;

my (@vals, @sub_vals, $total, @best_sub_vals);
my %opts = (m => 1024);
getopts(‘n:m:v’, \%opts);
if ($opts{‘n’}) {for (my $i = 0; $i < $opts{'n'}; $i++) {push @vals, int(rand($opts{'m'})) + 1}} else {foreach (<>) {chomp; push @vals, $_} $opts{‘n’} = $#vals + 1}
foreach (@vals) {$total += $_}
my ($sub_total, $half, $best) = (0, int($total / 2), 0);
print “Total:\t$total\tHalf:\t$half\tValues:\t”, join(” “, @vals), “\n\n”;

sub rec {
my $i = shift;
if ($i == $opts{‘n’}) {

if ($sub_total > $best) {
print “Subtotal: $sub_total\tSubvals: @sub_vals\n” if $opts{‘v’};
$best = $sub_total;
@best_sub_vals = @sub_vals;
if ($sub_total == $half) {print “Ideal solution found – quitting.\n”; exit}
}
return;
}
rec($i + 1);
return if $sub_total + $vals[$i] > $half;
$sub_total += $vals[$i];
push @sub_vals, $vals[$i];
rec($i + 1);
$sub_total -= $vals[$i];
pop @sub_vals;
}

rec 0;

END {
print “Subtotal: $best\tSubvals: @best_sub_vals\n”
}
[/perl]

The problem, of course, is that this simplistic algorithm runs in exponential time, since we are basically taking each of n donations independently and making a binary decision about it. Indeed, the question of whether there exists an exact solution, where the two recipients each receive precisely the same amount, is known as the Partition Problem; it is a subset of the Subset Sum Problem, which is in turn a subset of the Knapsack Problem. These problems are apparently known to be in general NP-complete, and since the decision versions are NP-complete, the optimization versions are NP-hard.

In 2008, Jorma Jormakka proved that “there does not exist a polynomial-time
algorithm to the the subset sum problem.”

On the other hand, on April 1, 2009, Doron Zeilberger “provided a polynomial time algorithm for the Subset Sum problem”, but he subsequently had to clarify that “you should add that this was meant as an April Fool’s Joke, since apparently, some people didn’t get that it was meant as a joke”. One giveaway might have been this paragraph:

A considerable speed-up can be achieved if one uses “analog” computations, namely an analytical balance easily obtained in any chemistry laboratory. First have the computer plot the real and imaginary parts of P(e ^ ix ), above −π < x < π, on high-quality paper. Second, print-out these two plots. Third, using scissors, for each of these plots, carefully cut the parts above and below the x-axis. Third, find the difference in weight between the positive and negative parts, and divide by the weight of a unit square. If the sum of the absolute values of the two differences is less than √2/2, then output no, otherwise yes.

Incidentally, Zeilberger is also one of the authors of Talmudic lattice path counting:

Naive counting counts by 1, Generatingfunctionology counts by z**n, sieves count by +1 or -1, but the Talmud counts by fractions.

The paper begins as follows:

Two are holding a talit, one is saying it is all his, and (the other one) is saying it is all his, … let them each get half. (Bava Metzia)

Consider all planar walks, with positive unit steps (1,0) and (0,1), from the origin (0,0) to a given point (a,b). Let L be the line joining the beginning to the end, i.e. the line bx-ay=0. Call the region below L “downtown”, and the region above L “uptown”, the line L being the border-line between downtown and uptown. Each such walk has a+b-1 points, not counting the endpoints. For i=0, … ,a+b-1, let Wi be the set of walks with “exactly” i points downtown and “exactly” a+b-1-i points uptown. How do we treat those walks that have some points on L? If there are i points downtown, and j points on L, then each of the sets Wi , Wi+1 , … , Wi+j have equal claim for this walk. If it is possible to divide a talit, then why not divide a walk. After the j+1 contesting sets take oaths that they each own at least 1/(j+1) of the contested walk, we declare that each gets exactly 1/(j+1) of that walk. It turns out that this way of distributing border-line (sic!) walks is as fair as can be, since we have:

Theorem: The sets Wi, i=0, … , a+b-1 are equi-numerous. …

The paper contains this interesting little footnote:

The third author [Zeilberger] grew up in Kiryat Motzkin, that was named after Theodore Motzkin’s father, Leo, the great Zionist leader. There are at least two other examples of Zionist leaders whose sons became combinatorialists: Ze’ev Jabotinsky, whose son Eri, was a professor of Mathematics at the Technion, and Alex Wilf, whose son is Herb Wilf.

Words Mean What We Want Them To Mean

A while ago, in the course of a conversation with an acquaintance who was engaged to be married, I referred to his “fiancée”. At the time, I was fairly new to that particular social milieu, and my acquaintance, probably assuming that I was unfamiliar with the vernacular, gently told me that “We say כלה here.” I had actually been well aware of that; the question is – is this usage legitimate?

In a similar vein, I was recently involved in an argument over the current Hebrew usage of the term אירוסין to refer to engagement, as opposed to its traditional meaning of formal betrothal, i.e. a stage of actual marriage, where adultery is punishable by death. I and others were unhappy with this redefinition of the term, particularly since we have traditionally had a perfectly good word for engagement: שידוכין. Others maintained that there was no problem – language evolves.

Ultimately, this is the classic prescriptivism vs. descriptivism debate. Recently, though, I discovered several sources showing that the above uses are actually centuries old, and are not merely corruptions of the modern era. And indeed, there are actually significant Halachic consequences to this, as we shall see.

Using “ארוס”and “ארוסה” To Refer To A משודך and משודכת

Rosh tells us that in the לשון העולם a betrothed woman is called “ארוסה”, and therefore a קול that a woman is an ארוסה does not require her to obtain a Get:

שאלה

ראובן שידך רבקה ושלח לה סבלונות

שאלו בני העיר למוליכי הסבלונות למי אתם מוליכים אלו הסבלונות אמרו לרבקה מאורסת ראובן הנזכר,

ויצא לה קול בעיר שהיא ארוסה לו.

ילמדנו רבינו אם הן אלו קדושין או ספק קידושין להצריכה גט כיון שיצא הקול בעיר שהיא ארוסתו.

תשובה

יראה שאין כאן קול להצריכה גט. דמשום סבלונות אין כאן מיחוש שנהגו בארץ הזאת דמסבלי והדר מקדשי,

ואי משום קול שהיו הנשים [אומרות] שהם מוליכות הסבלונות לרבקה ששלח לה ארוסה ראובן, לאו קול הוא להצריכה גט שכן לשון העולם לקרות למשודכת ארוסה. …1

Referring To An Engaged Couple as חתן וכלה

In a similar vein, the Aharonim explain that just because a betrothed couple have been referred to as חתן וכלה does not mean that they are actually married, since, once again, בלשון העולם these terms are used even for couples who are merely engaged:

וכל זה [דחוששין לסבלונות ומצריכים גט על פי תנאים מסויימים] ששולח סתם אבל אם פירש בהדיא ששולח לה לשם סבלונות ליכא למיחש לפרש”י וכל שכן אם אמר ששולח לשם דורון בעלמא אפילו אמר שהחתן שלח לכלה2

שהחתן שלח לכלה. כלומר ואין לשון חתן וכלה מורה על קידושין דגם משודך ומשודכת נקראים חתן וכלה בלשון העולם:3

שהחתן שולח לכלה. דמשודכת נקראת גם כן בלשון כלה:4

That Old-Time Religion

On the other hand, there is an opinion that rails against the new-fangled custom of newspaper and other types of engagment anouncements that use the term מאורשים, arguing that it should not be used for engaged couples, for exactly the abovementioned reason, to avoid the generation of a קול:

מה שנשתרבב המנהג בזמן האחרון כשמודיעים בעתונים או על ידי פתקאות ומכתבים גלויים מקישור תנאים של החיתון, מדפיסים פלוני ופלוני “מאורשים”, זה לא נכון דלשון אירוסין בלשון התורה וגמרא, וגם אחר חתימת התלמוד, וגם עד דורנו האחרון, קוראים לקידושין אירוסין, ולא לעשיית תנאים, אם כן בוודאי לא נכון לכתחלה לומר על קישור תנאים לבד שנעשה אירוסין.

ולכתחילה יש לחוש למה שכתוב במשנה שלהי מסכת גיטין דף פ”ח ע”ב יצא שמה בעיר מקודשת, מקודשת, ולפעמים על ידי כמה סיבות נתבטל השידוך, ולמה נפרסם בעולם שהיא מקודשת בעוד שאין כאן אפילו ריח קידושין.5

As we have seen, the claim that “even after the sealing of the Talmud, until this latest generation, קידושין are called אירוסין, but the drawing up of the תנאים are not” is simply incorrect.

  1. שו”ת הרא”ש (מכון אור המזרח / מכון ירושלים: תשנ”ד) כלל ל”ה סימן י”ב, הובאו דבריו בבית יוסף אה”ע סימן מ”ו ובחלקת מחוקק שם ס”ק י”א []
  2. הגהת רמ”א שם סימן ריש מ”ה []
  3. חלקת מחוקק שם ס”ק ד’, ועיין גם דבריו בסימן מ”ו ס”ק י”א []
  4. בית שמואל שם ס”ק ו []
  5. נטעי גבריאל (שידוכים – תנאים) פרק כ”ג הערה כ”ו בשם “קול אריה (נישואין)”‏ []

More Than Four Wives

Reuters reports (via Religion Clause):

Lashes for Saudi religious policeman with six wives

Wed Feb 17, 2010 4:09pm IST

RIYADH (Reuters) – A Saudi court has sentenced an employee of the kingdom’s religious police to 120 lashes for marrying six women.

The man said he was not educated enough to know that Islam does not allow men to marry more than four women at any one time, said an official at Ahad al-Massarha court in the southern province of Jazan.

“The judge did not believe him. Nobody believed him. I honestly did not,” the official told Reuters.

The court banned the man from standing as a preacher and leading prayers, ordered him not to travel abroad for a five-year period and to memorise two chapters from the Koran. …

Islam allows polygamy for men on condition the wives are treated fairly.

In Halachah, the four wife limit is merely advisory, but not mandatory (in times / places where the חרם דרבינו גרשום and similar enactments, customs and personal commitments do not apply):

נושא אדם כמה נשים והוא דאפשר למיקם בסיפוקייהו

ומכל מקום נתנו חכמים עצה טובה שלא ישא אדם יותר מד’ נשים כדי שיגיע לכל אחת עונה בחודש

ובמקום שנהגו שלא לישא אלא אשה א’ אינו רשאי לישא אשה אחרת על אשתו:

רבינו גרשום החרים על הנושא על אשתו אבל ביבמה לא החרים וכן בארוסה:1

Helkas Mehokek maintains that the woman may waive the condition of אפשר למיקם בסיפוקייהו:

יש להסתפק אם האיסור היא מצד האשה שהיא יכולה למחות בידו מאחר שאין יכול לקיים לה שאר וכסות ועונה או נימא דאף היא מתרצה לו ונותנה לו רשות לישא אחרת הבית דין מוחין לו אם אינו יכול להספיק אותם

ומדברי הרמב”ם (פרק ט”ו מהלכות אישות) הביאו הטור (בסימן (ע”ז) [ע”ו] ס”ק ד’) משמע דתלוי ברצון הנשים וכן משמע בתשובת הריב”ש סימן צ”א

ומקרא מלא הוא (והחזיקו שבע נשים באיש אחד ביום ההוא לאמר לחמינו נאכל ושמלותינו נלבש רק יקרא שמך עלינו אסוף חרפתינו ישעיה ד’) וכל דבר שבממון תנאו קיים:2

Beis Shmuel concurs, but adds that in the case of a Yevamah, the court must counsel her against the marriage:

הנה אם היא מוחלת ורצונה להסתפק במיעוט בוודאי רשאי לישא אפילו אם אי אפשר למיקם בסיפוקייהו וכן כתב בחלקת מחוקק

מיהו ביבמה נראה אפילו אם היא מוחלת מכל מקום מוטל על הבית דין ליתן לה עצה טובה שאל תנשא לו …3

  1. שולחן ערוך אה”ע סימן א’ סעיפים ט’ – י []
  2. חלקת מחוקק שם ס”ק י”ג []
  3. בית שמואל שם ס”ק י”ח []